Fermat: Los dos últimos dígitos de $7^{355}$

Question

Estoy haciendo este problema mencionado anteriormente y sé la respuesta porque conozco el Teorema de Euler que $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$ Usé 100 como módulo y obtuve que los dos últimos dígitos de $7^{355}$ son $43$ .

Mi pregunta es la siguiente. ¿Qué primo debo elegir para resolver este problema utilizando el teorema de Fermat $$a^{p-1}\equiv{1}\pmod{p}$$ Como problema precursor, el autor (Dudley; Elementary Number Theory) pidió encontrar la última cifra del número anterior; así que usando un módulo $5$ , $7^4\equiv{1}\pmod{5}$ por Fermat. Como la respuesta es $7^{355}\equiv{3}\pmod{5}$ el último dígito es $3$ o $8$ . Desde $7$ es impar, la respuesta será claramente impar, por lo que $3$ es. El libro trabaja de forma lineal, construyendo a partir de los capítulos anteriores, y el Teorema de Euler no se menciona hasta dentro de dos capítulos (recordaba a Euler de una clase de resolución de problemas en la universidad).

Así que, de nuevo, ¿qué prima sería mejor? ¿Cómo debo proceder?

EDIT: He visto un montón de problemas en la web y ninguno de los que he mirado lo hacía usando Fermat. Si hay uno, que podría ser publicado y yo sería feliz.

EDIT 2: parece que el problema de encontrar los dos últimos dígitos utilizando es bastante difícil debido a la implicación de que necesitamos algo mod 100. ¿Hay alguna manera de evitar esto, como la adición de un paso o complexifying, con el fin de terminar el problema con Fermat?

Answer 1

Cuadratura repetida

Si no se mencionara a Euler lo consideraría un problema de cuadratura repetida: $$\begin{align} 7^2&\equiv 49\\ 7^4&\equiv 49^2\equiv 1\\ 7^8&\equiv 1^2\equiv 1\\ 7^{(2^n)}&\equiv 1\mbox{ for }n>1 \end{align}$$ Ahora $355=101100011_2=2^8+2^6+2^5+2^1+2^0$ y por lo tanto $$\large \begin{align} 7^{355}&=7^{2^8+2^6+2^5+2^1+2^0}\\ &\equiv7^{2^1+2^0}\\ &=343\\ &\equiv 43 \end{align}$$

Enfoque de remanente chino

Conocer el Teorema del Resto Chino simplifica entonces el tamaño de los cálculos ya que módulo 25 tenemos $7^2\equiv -1$ y $7^{4k}\equiv 1$ y por lo tanto $7^{355}\equiv 7^3\equiv -7$ módulo 25.

Al mismo tiempo tenemos $7^2\equiv 1$ módulo 4 para que $7^{355}\equiv 7\equiv 3$ módulo 4. Ahora $25\equiv 1$ módulo 4 y $-24\equiv 1$ modulo 25 así que $$7^{355}\equiv 3\cdot 25-7\cdot (-24)$$ módulo 100 debido al Teorema del Resto Chino. Terminando este cálculo obtenemos $$3\cdot 25-7\cdot(-24)=10\cdot 25-7=243$$ para ver que $7^{355}\equiv 243\equiv 43$ modulo 100.

Answer 2

Utiliza los primos 2 y 5 y combina los resultados utilizando el teorema del resto chino para obtener la última cifra.

Answer 3

Sugerencia $\rm\ mod\ 100\!:\ \color{#c00}{7^4} \overset{\,}\equiv (50-1)^2 \equiv \color{#c00}1\ $ así que $\rm\ 7^N = 7^{\,4J+K}\!\equiv (\color{#c00}{7^4})^J 7^K\equiv \color{#c00}1^J7^K\!\equiv 7^K$

Dicho de forma equivalente $\rm\ 7^{\large\color{#0a0}4}\equiv 1\, \Rightarrow\, 7^{\large N}\equiv 7^{\large K}\ (mod\ 100)\ $ si $\rm\ K\,\equiv\, N\ \ (mod\ \color{#0a0}4).\,$ Para simplificar la aritmética, elija el más pequeño de tales $\rm\,K > 0,\ $ a saber: $\rm\ \: K \,= (N\ \,mod\,\ \color{#0a0}4).\,$ Ver también esta respuesta.