Exponenciación Modular mediante el teorema de Euler

Question

¿Cómo puedo calcular el $27^{41}\ \mathrm{mod}\ 77$ tan simple como sea posible?

Ya sé que $27^{60}\ \mathrm{mod}\ 77 = 1$, por el teorema de Euler:

$$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$ y $$ \phi(77) = \phi(7 \cdot 11) = (7-1) \cdot (11-1) = 60 $$

También sé de uso de exponenciación modular que $27^{10} \mathrm{mod}\ 77 = 1$ y por lo tanto

$$ 27^{41}\ \mathrm{mod}\ 77 = 27^{10} \cdot 27^{10} \cdot 27^{10} \cdot 27^{10} \cdot 27^{1}\ \mathrm{mod}\ 77 = 1 \cdot 1 \cdot 1 \cdot 1 \cdot 27 = 27 $$

Pero puedo derivar el resultado de $27^{41}\ \mathrm{mod}\ 77$ $27^{60}\ \mathrm{mod}\ 77 = 1$ de alguna manera?

Answer 1

Si usted es serio acerca de "tan simple como sea posible", a continuación, observe que $27^{41} = 3^{123}$ y el uso del teorema de Carmichael (un fortalecimiento de el teorema de Euler que en realidad le da un apretado unido) a deducir que $3^{30} \equiv 1 \bmod 77$ y, por tanto,$3^{123} \equiv 3^3 \equiv 27 \bmod 77$. Pero yo creo que esta no es la pregunta correcta; que realmente debería estar haciendo "tan general como sea posible," y, a continuación, la respuesta que usted ha aceptado es el más apropiado.

(Por supuesto, basta con usar el teorema de Euler para el cálculo anterior, pero pocas personas parecen aprender del teorema de Carmichael y me gusta siempre a punto de salir cuando puedo.)

Answer 2

Como se sugiere en el comentario anterior, puede utilizar el Teorema del Resto Chino, mediante el teorema de Euler / teorema de Fermat en cada uno de los números primos por separado. Usted sabe que $27^{10} \equiv 1 \mod 11$, y también se puede ver que el modulo 7, $27 \equiv -1 \mod 7$, lo $27^{10} \equiv (-1)^{10} \equiv 1\mod 7$. Por lo $27^{10} \equiv 1 \mod 77$, e $27^{41} = 27^{40+1} \equiv 27 \mod 77$. (En realidad hemos encontrado la orden de 27 de 10, pero un procedimiento mecánico, se puede usar ese $27^{41} \equiv 27 \equiv 5 \mod 11$ $27^{6} \equiv 1 \mod 7$ a ver que $27^{41} = 27^{42-1} \equiv 27^{-1} \equiv -1 \mod 7$, y poner 5 mod 11 y -1 mod 7, junto a obtener 27.)

Esto es si se hacen a mano, para este caso. En general, a través de algoritmos, solo que el uso repetido de cuadratura para exponentiate números. No mucho que ganar mediante el teorema de Euler, dado que la búsqueda de la orden de un número de mod $n$ es tan duro como el factoring $n$.

Answer 3

Puede utilizar la exponenciación al cuadrado (todas las operaciones son el modulo 77):

$27^{41} = 27^{32+8+1} = 27 \cdot 27^8 \cdot (27^8)^4 = (*)$

$\big[ 27^8 = ((27^2)^2)^2 = (36^2)^2 = 64^2 = 15 \big]$

$(*) = 27 \cdot 15 \cdot 15^4 = 27 \cdot 15 \cdot (15^2)^2 = 27 \cdot 15 \cdot 71^2 = 27 \cdot 15 \cdot 36 = 27$

Este utiliza sólo el 7 multiplicaciones en lugar de 41.

Answer 4

A poco de Fermat: $\; 6,10\:|\:120\ \Rightarrow\ 3^{120} \equiv 1 \pmod{7, 11}\ \Rightarrow\ 3^{123} \equiv 3^3 \pmod{77}$

Vea también estos Fermat-Euler-Carmichael generalizaciones de poco Fermat-Euler de mi lesión.matemáticas post en 10 de abril de 2009.

TEOREMA 1 $\ $ Por productos naturales $\rm\: a,e,n\: $ $\rm\: e,n>1 $

$\rm\qquad\qquad\ n\ |\ a^e-a\ $ todos los $\rm\:a\ \iff\ n\:$ es squarefree y el primer $\rm\: p\:|\:n\: \Rightarrow\: p-1\ |\ e-1 $

COMENTARIO $\ $ El caso especial $\rm\:e \:= n\:$ es Korselt el criterio de los números de Carmichael.

TEOREMA 2 $\ $ Por productos naturales $\rm\: a,e,n \:$ $\rm\: e,n>1 $

$\rm\qquad\qquad\ n\ |\ a^e-1\ $ todos los $\rm\:a\:$ coprime a $\rm\:n\ \iff\ p\:$ prime, $\rm\ p^k\: |\: n\ \Rightarrow\ \lambda(p^k)\:|\:e $

con $\rm\quad\ \lambda(p^k)\ =\ \phi(p^k)\ $ para los impares primos $\rm\:p\:,\:$ o $\rm\:p=2,\ k \le 2 $

y $\quad\ \ \rm \lambda(2^k)\ =\ 2^{k-2}\ $ $\rm\: k>2 $

La última excepción es debido a $\rm\:\mathbb Z/2^k\:$ tener multiplicativo grupo $\rm\ C(2) \times C(2^{k-2})\ $ $\rm\:k>2\:.$

Tenga en cuenta que al menos exponente $\rm\:e\:$ está dado por $\rm\: \lambda(n)\: =\: lcm\ \{\lambda(\;{p_i}^{k_i})\}\;$ donde $\rm\ n = \prod {p_i}^{k_i}\:.$

$\rm\:\lambda(n)\:$ se llama el (universal) exponente del grupo de $\rm\:\mathbb Z/n^*,\:$.k.una. el Carmichael función.

Ver mi post aquí para pruebas y posterior debate.