Congruencia con un módulo de primera potencia

Question

¿Cómo podría calcular: 5^11469 mod 1911?

Lo que sé:

1911 no es primo porque es divisible por 3. Lo mismo ocurre con el exponente 11469. Como ambos números son divisibles por 3, ¿puedo reducir el problema a 5^3823 mod 637? A partir de aquí, 637 tampoco es primo. Por otro lado, el exponente es primo.

¿Tendré que reducirlo de alguna manera para poder utilizar el Pequeño Teorema de Fermat?

Por favor, avisa.

Gracias.

Answer 1

Lo harías, tomando nota de ello:

• 1911 tiene 1008 números que no comparten un factor con él
• 11469 tiene un resto de 381 en la división por 1008
• utilizar las reglas de los exponentes repetidos para potenciar ese punto

De forma equivalente se podría anotar:

• tiene un resto de 2 en la división por 3 ( aka de la forma $3x+2$ )
• tiene un resto de 27 en la división por 49 (de la forma $49y+27$ )
• tiene resto de 5 en la división por 13 ( aka de la forma $13z+5$ )

Igualando los tres anteriores, podemos resolver las formas de $x$ , $y$ y $z$ ( $y$ es 3 mod 13 y 2 mod 3 lo que lleva a que sea 29 mod 39 por ejemplo) resolviendo un resto único en la división por 1911 ( obtenemos 1448 mod 1911)