Un rompecabezas con potencias y tetration mod n

Question

Hace poco, un amigo me preguntó si podía resolver estos tres problemas:

(a) Demuestre que la secuencia $ 1^1, 2^2, 3^3, \dots \pmod{3}$ En otras palabras $\{n^n \pmod{3} \}$ es periódica, y hallar la longitud del período.

(b) Demuestre que la secuencia $1, 2^2, 3^{3^3},\dots \pmod{4}$ es decir $\{\ ^nn \pmod{4}\}$ es periódica y hallar la longitud del período.

(c) Demuestre que la secuencia $1, 2^2, 3^{3^3},\dots \pmod{5}$ es decir $\{\ ^nn \pmod{5}\}$ es periódica y hallar la longitud del período.

Los dos primeros no eran terriblemente difíciles (pero podrían ser ejercicios útiles en la pequeña teorema de Fermat), pero el tercero me está causando problemas, ya que mis métodos están llevando a un montón de casos individuales, y me interesaría ver si alguien aquí puede encontrar una forma más ordenada de resolverlo.

(En (c), he evaluado los primeros 15 términos, y no he encontrado ningún punto todavía - a menos que me haya equivocado).

Answer 1

Necesitaremos la siguiente ligera generalización del teorema del totiente: $a^{k + \varphi(n)} \equiv a^k \bmod n$ para todos $a$ siempre que $k$ es al menos tan grande como el mayor exponente de la factorización de primos de $n$ .

De ello se desprende que

$$a^b \equiv a^{b \bmod 4} \bmod 5$$

siempre que $b \ge 1$ y

$$b^c \equiv b^{c \bmod 2} \bmod 4$$

siempre que $c \ge 2$ (donde tenemos que tomar el resto en $\{ 2, 3\}$ ). Por último,

$$c^d \equiv c \bmod 2$$

siempre que $d \ge 1$ . En resumen,

$$a^{b^{c^d}} \equiv a^{b^c} \bmod 5$$

siempre que $b \ge 1, c \ge 2, d \ge 1$ . Pero esta expresión sólo depende del valor de $a \bmod 5, b \bmod 4, c \bmod 2$ por lo que la secuencia en cuestión tiene un periodo eventual que divide $20$ y basta con calcular los primeros términos para demostrar que el periodo final es un periodo real. Un argumento similar funciona para $5$ sustituido por cualquier número entero positivo $m$ (pero no hay garantía de que el período eventual sea un período real en esta generalidad y espero que esto sea falso); obtenemos que el período eventual divide $\text{lcm}(m, \varphi(m), \varphi(\varphi(m)), ...)$ . Y, por supuesto, podemos sustituir $\varphi(m)$ por el Función de Carmichael para los más grandes $m$ para obtener mejores resultados.

Answer 2

Para $k\ge 1$ tenemos

$$\begin{align*} {^{k+2}n}\bmod5&=(n\bmod5)^{^{k+1}n}\bmod5=(n\bmod5)^{^{k+1}n\bmod4}\bmod5\\ {^{k+1}n}\bmod4&=(n\bmod4)^{^kn}=\begin{cases} 0,&\text{if }n\bmod2=0\\ n\bmod4,&\text{otherwise}\;, \end{cases} \end{align*}$$

así que

$${^{k+2}n}\bmod5=\begin{cases} (n\bmod5)^0=1,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

En particular,

$${^nn}\bmod5=\begin{cases} (n\bmod5)^0,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

para $n\ge3$ , donde $0^0\bmod5$ se entiende que $0$ . Es evidente que el período que comienza en $n=3$ es un múltiplo de $20$ El cálculo real muestra que es $20$ y que no podemos incluir los dos primeros términos::

$$\begin{array}{r|c|c} n:&&&&&&&&&1&2\\ {^nn}\bmod5:&&&&&&&&&1&4\\ \hline n:&3&4&5&6&7&8&9&10&11&12\\ {^nn}\bmod5:&2&1&0&1&3&1&4&0&1&1\\ \hline n:&13&14&15&16&17&18&19&20&21&22&\\ {^nn}\bmod5:&3&1&0&1&2&1&4&0&1&1 \end{array}$$

( Añadido: Y no, no había visto que Qiaochu ya había respondido a la pregunta hasta después de haber posteado).