Demostrar que $ 5^{2^{x}} \equiv 1 \pmod {17} $ para todos $ x \in \mathbb{N}_{> 3} $ .

Question

¿Cómo puedo demostrar la siguiente identidad de congruencia?

$ \forall x \in \mathbb{N}_{> 3}: \qquad 5^{2^{x}} \equiv 1 \pmod {17} $ .

Lo he verificado numéricamente para $ x $ hasta (al menos) $ 10000 $ pero no puedo entender por qué es cierto.

Este es un código de Python que verifica esta propiedad:

for X in xrange(10000):
    if pow(5,pow(2,X),17) != 1:
        print X

Answer 1

Sugerencia : paso de inducción $$ 5^{(2^{x+1})}=5^{2^x+2^x}=5^{2^x}\times5^{2^x}\equiv1\times 1\pmod{17}. $$

Answer 2

SUGERENCIA: $\phi(17) = 16$ divide $2^x$ para $x>3$ , donde $\phi$ es la Función Totiente de Euler.

Answer 3

Lo que estás realizando es, de hecho, una "exponenciación continuada". Esto se puede ver en la ecuación $5 ^{2^x} = ((5 \overbrace{^2)^2)\ldots}^{\text{x times}} )^2$ . Así que es de esperar que una vez que lleguemos a $1$ el resultado sigue siendo $1^2=1$ . En general, el uso de otros números de base que $5$ otros exponentes que $2$ y otros módulos que $17$ produce hermosos gráficos en forma de copo de nieve, véase Contexto.pdf .

Answer 4

Tenga en cuenta que $5^{2^4}=5^{17-1}$ por lo tanto, por FLT: $5^{2^4}\equiv1\pmod{17}$ .

Podemos utilizar esta observación para demostrar por inducción.

---

Primero, demuestre que esto es cierto para $x=4$ :

Hemos demostrado que $5^{2^4}\equiv1\pmod{17}$ Por lo tanto $5^{2^4}=17n+1$ .

En segundo lugar, supongamos que esto es cierto para $x$ :

Suponemos que $5^{2^x}\equiv1\pmod{17}$ Por lo tanto $5^{2^x}=17k+1$ .

Tercero, demostrar que esto es cierto para $x+1$ :

$5^{2^{x+1}}=$

$(\color\red{5^{2^x}})^2=$

$(\color\red{17k+1})^2=$

$289k^2+34k+1=$

$17(k^2+2k)+1$

Hemos demostrado que $5^{2^{x+1}}=17(k^2+2k)+1$ Por lo tanto $5^{2^{x+1}}\equiv1\pmod{17}$ .

---

Tenga en cuenta que el supuesto sólo se utiliza en la parte marcada en rojo.

Answer 5

El teorema de Fermat-Euler

Si $\gcd(a,m)=1$ y que $\varphi(x)$ denotan la función de Euler, entonces $$a^{\varphi(m)}\equiv1\pmod m.$$

Ahora, ponte $m=17$ y $a=5$ .