Solución de problema 8.2 de la tarea num. 5

El problema:

Sea N un entero > 1 libre de cuadrados (no tiene divisor cuadrado mayor que 1; o en otras palabras, es un producto de primos distintos). Demuestra que para cualquier dos enteros positivos n₁ y n₂, a ^n₁ es congruente con a ^n₂ (mod N), si n₁ es congruente con n₂ (mod f), donde f:=fi(N).

Solución:

Sea N'=N/(a, N). Entonces la condición "libre de cuadrados" implica (a, N')=1 (ejercicio fácil).

Sea f':=fi(N'), así que tenemos, por el Teorema de Euler-Fermat, que a ^f' es congruente con 1 (mod N').

Ahora un lemma: N' | N implica f' | f. (Demostracion al final).

Suponemos (sin perdida de generalidad) que n₁ > n₂ > 0. Como f | n₁ - n₂, tenemos (por el lemma) que f' | n₁ - n₂, así que a ⁿ₁ - n₂ es congruente con 1 (mod N'), o sea a ⁿ₁ - n₂ - 1 = lN' para algun entero l. Multiplicando la última igualdad por a ^n₂ obtenemos que a ^n₁ - a ^n₂ = lN'a ^n₂ ; pero el último es claramente divisible entre N.

Demostración del lemma: Para N de la forma p^a, N' es de la forma p^a' con a' < a, y el inciso sigue del hecho que p^a' - p^{a' -}1 divide a p^a - p^{a -}1. El caso general sigue facilmente de este caso y la propiedad multiplicativa de fi(N).

Otra demostración del lema (usando ideas de la teoria de grupos) : definimos un homomorfismo Z_N^* --> Z_N'^* por x mod N |--> x mod N'. Hay que checar que esto está (1) bien definido, (2) un homomorfismo y (3) sobre. Esto implica que Z_N'^* es isomorfo a un grupo cociente de Z_N^*, y de aqui sigue el inciso (usando el teorema de Lagrange).