Problemas elementales de la teoría de números

Question

Estoy tratando de resolver los dos problemas siguientes:

Espectáculo $n^{12}\equiv 1\pmod{72}$ al $(72,n)=1$

y

Calcular ${7^8}^9\pmod{100}$

Para la primera, vi que $n^{24}=n^{\varphi(72)}\equiv1\pmod{72}$ por el teorema de Euler, pero esto nos deja con $n^{12}n^{12}\equiv 1\pmod{72}$. Esto podría significar $n^{12}\equiv 1\pmod{72}$ o $n^{12}\equiv 71\pmod{72}$. No estoy seguro de cómo argumentar correctamente a la conclusión de que es sólo $n^{12}\equiv 1\pmod{72}$.

Para el segundo, prácticamente me hizo la fuerza bruta. ${7^8}^9\pmod{100}$ puede ser resuelto mediante la consideración de $8^{9}\pmod{\varphi(100)=40}$. Desde $8$ es cíclica con el fin de $4: 8^5\equiv 8\pmod{40}$, sabemos $8^9=8^5\cdot8^4\equiv 8^5\equiv 8$. Así que busque en $7^8\pmod{100}$. 7 también es cíclico con $7^4\equiv 1\pmod{100}$. Por lo $7^8=(7^4)^2\equiv 1\pmod{100}$. Yo sabía que estos "cíclica" las cosas de forma manual la informática y la reducción, sin embargo.

Gracias por cualquier ayuda... (nota: esto no es la tarea)

Answer 1

Para el primero, se nota que, aunque $\phi(8)=4$, de hecho es verdad que $\gcd(n,8)=1$ implica $n^2\equiv1\pmod8$. Si usted piensa, verás que es por eso que usted puede conseguir lejos con 12 cuando se trabaja mod 72, en lugar de tener 24.

EDIT: elaboración en respuesta a OP comentario:

$\gcd(n,8)=1$ implica $n^2\equiv1\pmod8$, lo que implica $n^6\equiv1\pmod8$.

$\gcd(n,9)=1$ $\phi(9)=6$ implica $n^6\equiv1\pmod9$.

Los últimos dos congruencias implican $n^6\equiv1\pmod{72}$, lo que sin duda implica la necesaria $n^{12}\equiv1\pmod{72}$.

Answer 2

Para el problema 2, usted puede hacer mejor que comprobar manualmente utilizando el Teorema del Resto Chino.

En efecto, primero se desea calcular $x^9$ modulo $\phi(100)=\phi(2^2\times 5^2) = 2\times 4\times 5$. Pero el trabajo del modulo $40$ es equivalente, por el Teorema del Resto Chino, para trabajar modulo $8$ y el modulo $5$. La ventaja es que $8^9\equiv 0 \pmod{8}$, e $8^9 \equiv 8\pmod{5}$ (desde $\varphi(5)=4$, lo $8^4\equiv 1\pmod{5}$). Desde $8^9\equiv 8\pmod{8}$$8^9\equiv 8\pmod{5}$, entonces se sigue que $8^9\equiv 8\pmod{40}$.

Entonces usted puede hacer lo mismo con $7^8\pmod{100}$. De trabajo modulo $4$ tenemos $7^8\equiv (-1)^8 \equiv 1\pmod{4}$, y de trabajo modulo $25$ tenemos $7^8\equiv (49)^4\equiv (-1)^4\equiv 1\pmod{25}$. Por lo $7^8\equiv 1\pmod{100}$, y hemos terminado.

El primer problema es asimismo más simple de hacer por trabajo modulo $8$ y el modulo $9$ por separado, y luego aplicando el Teorema del Resto Chino.

Answer 3

$(1)$ El uso de Carmichael función, $$\lambda(72)=\text{lcm}(\lambda(8),\lambda(9))=\text{lcm}(2,6)=6$$

$$\implies n^6\equiv1\pmod{72}\text{ if }(n,72)=1 $$

$(2)$ Observa que el $\displaystyle7^2=49=50-1\implies 7^4=(50-1)^2=50^2-2\cdot50\cdot1+1\equiv1\pmod{100}$

$\displaystyle\implies7^n\equiv1\pmod{100}$ si $4|n$

Ahora, $8^9=(2^3)^9=2^{27}$