Uso del teorema de Euler para determinar el remanente

Question

Estoy haciendo un autoestudio en teoría de números.

Uno de los ejercicios me ha dejado perplejo:

Encuentra el resto de 34 82248 dividido por 83. (Pista: Teorema de Euler).

Sé que 34 y 83 son primos relativos (y por extensión 34 82248 y 83), o que gcd(34, 83) = 1 .

Alguien ya ha hecho esta pregunta ( Utilizar el Teorema de Euler para encontrar los restos ), pero no creo que la respuesta dada sea correcta (sugieren que es 77, y python dice que es 4). Sé que las preguntas repetidas son un pecado mortal del intercambio de pilas; pero estoy reformulando la pregunta con un poco más de detalle con la esperanza de que alguien pueda iluminarme. Si hay una forma mejor de obtener una respuesta satisfactoria a la pregunta, la adoptaré con gusto.

Answer 1

Puede verificar la respuesta rápidamente con un simple mental aritmética de la siguiente manera:

Por el teorema de Euler sabemos que $\, \color{#c00}{34^{82}\equiv 1}\pmod{83}$

Nota $\,{\rm mod}\ 82\!:\ 82248 \equiv 248\equiv 3(82)+2\equiv 2,\ $ así que $\,\ 82248 = 2+82 N$

Así, ${\rm mod}\ 83\!:\ 34^{\large 82248}\!\equiv 34^{\large 2+82N}\!\equiv 34^{\large 2} (\color{#c00}{34^{\large 82}})^{\large N}\!\equiv 34^{\large 2} \color{#c00}1^{\large N}\!\equiv 34^{\large 2}$

y $\ 34^2 \equiv 2^2 17^2\equiv 68\cdot 17\equiv -15\cdot 17\equiv -3\cdot 85\equiv -3(2)\equiv -6$

Answer 2

Por el Teorema de Euler (o de Fermat), $34^{82}\equiv 1$ mod( $83$ ). Por lo tanto, $34^{82246}=34^{(82)(1003)}\equiv1$ mod( $83$ ). Por lo tanto, la respuesta requerida es el residuo de $34^2$ mod ( $83$ ) que se encuentra fácilmente $77$