¿Por qué el resto es diferente para 2 ^ 66/65 cuando se resuelve mediante dos métodos diferentes, el teorema del resto y el pequeño teorema de Fermet?

Answer 1

[matemáticas] 2 ^ {66} \ equiv (2 ^ 6) ^ {11} \ equiv (64) ^ {11} \ equiv (-1) ^ {11} \ equiv -1 \ equiv 64 \ pmod {65} [/matemáticas]

El pequeño teorema de Fermat dice para primo [matemáticas] p [/ matemáticas] y [matemáticas] a \ not \ equiv 0 \ pmod p, [/ matemáticas]

[matemáticas] a ^ {p-1} \ equiv 1 \ pmod {p} [/ matemáticas]

[matemática] 65 = 5 \ cdot 13 [/ matemática] no es primo, por lo que el pequeño teorema de Fermat no se aplica. Ese puede ser tu problema. En este caso, necesitamos usar la generalización, la función totiente de Euler:

[matemáticas] a ^ {\ phi (n)} \ equiv 1 \ pmod n [/ matemáticas]

[math] \ phi (n) [/ math] es el número de números naturales hasta [math] n [/ math] que son relativamente primos para [math] n [/ math]. Cuando [math] n [/ math] es primo, [math] \ phi (n) = n-1 [/ math] y esto se reduce al pequeño teorema de Fermat.

La fórmula del producto de Euler para la función totient es

[matemáticas] \ displaystyle \ phi (n) = n \ prod_ {p | n} \ left (1 – \ dfrac 1 p \ right) [/ math]

donde el producto se hace cargo de los distintos factores primos de [math] n. [/ math]

[matemáticas] \ phi (65) = 65 (1 – \ dfrac 1 5) (1 – \ dfrac 1 {13}) = 48 [/ matemáticas]

Entonces

[matemáticas] 2 ^ {48} \ equiv 1 \ pmod {65} [/ matemáticas]

[matemáticas] 2 ^ {66} \ equiv 2 ^ {66-48} \ equiv 2 ^ {18} \ equiv (2 ^ 6) ^ 3 \ equiv (-1) ^ 3 \ equiv -1 \ equiv 64 \ pmod {65} \ quad \ marca de verificación [/ math]