Verificación de números de Carmichael

Question

Estoy tratando de entender una solución que me dieron en un tutorial respecto a un problema con los números de Carmichael y me preguntaba si me pueden ayudar a aclarar las cosas:

Un número compuesto $m$ se llama a un número de Carmichael si la congruencia $a^{m-1} \equiv 1 \pmod{m}$ es cierto para cada número un con $\gcd(a,m) = 1$.

Compruebe que $m = 561 = 3 \times 11 \times 17$ es un número de Carmichael.

Solución:

Aplicar de Fermat Poco Teorema para cada divisor primo de $m$: \begin{align*} a^2 &\equiv 1 \pmod{3}\\ a^{10} &\equiv 1 \pmod{11}\\ a^{16} &\equiv 1 \pmod{17} \end{align*} De alguna forma esto implica que $a^{80} \equiv 1 \pmod{561}$, a continuación, en consecuencia,$a^{560} \equiv 1 \pmod{561}$.

Estoy perdido en cuanto a cómo el 3 congruencias implica $a^{80} \equiv 1 \pmod{561}$ ($80 = \mathrm{LCM}(2,10,16)$).

Puede alguien aclarar esto para mí?

Gracias!

Answer 1

Tenga en cuenta que $80 = \mathrm{lcm}(2,10,16)$. Así que usted puede escribir $a^{80} = (a^2)^{40} = (a^{10})^{8} = (a^{16})^5$. Así, \begin{align*} a^{80}= (a^2)^{40} &\equiv 1^{40} = 1\pmod{3},\\ a^{80}= (a^{10})^{8} &\equiv 1^8 = 1 \pmod{11},\\ a^{80}= (a^{16})^5 &\equiv 1^5 = 1\pmod{17}. \end{align*}

Por el Teorema del Resto Chino, el sistema de congruencias \begin{align*} x&\equiv 1\pmod{3}\\ x&\equiv 1\pmod{11}\\ x&\equiv 1\pmod{17} \end{align*} tiene una única solución modulo $3\times 11\times 17 = 561$. Pero tanto en $x=1$ $x=a^{80}$ son soluciones. Ya que la solución es única modulo $561$, luego las dos soluciones se encontró deben ser congruentes. Es decir, $$a^{80}\equiv 1\pmod{561}.$$

(Añadido. O, más simplemente, como Andrés señala, desde $3$, $11$, y $17$ cada división de $a^{80}-1$, y son pares de primos relativos, entonces su producto se divide $a^{80}-1$).

Una vez que usted tiene que $a^{80}\equiv 1\pmod{561}$, entonces el poder de $a^{80}$ es también congruente $1$ modulo $561$. En particular, $$a^{560} = (a^{80})^{7} \equiv 1^7 = 1 \pmod{561}$$ como se desee.

Answer 2

Nota $\: $ % primos $\rm\ p\neq q\:$coprime $\rm\:a\:,\:$ si $\rm\ p-1,q-1\ |\ m\ $ y $\rm\ p,q\ |\ a^m - 1\ \Rightarrow\ pq\ |\ a^m - 1$ desde lcm = producto de enteros coprimos (aquí primos distintos).