Prove that $ 5^{2^{x}} \equiv 1 \pmod {17} $ for all $ x \in \mathbb{N}_{> 3} $.

Question

How can I prove the following congruence identity?

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

I have numerically verified it for $ x $ up to (at least) $ 10000 $, but I cannot understand why it is true.

This is some Python code verifying this property:

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

Answer 1

Note that $5^{2^4}=5^{17-1}$, hence by FLT: $5^{2^4}\equiv1\pmod{17}$.

We can use this observation in order to prove by induction.

---

First, show that this is true for $x=4$:

We've shown that $5^{2^4}\equiv1\pmod{17}$, hence $5^{2^4}=17n+1$.

Second, assume that this is true for $x$:

We're assuming that $5^{2^x}\equiv1\pmod{17}$, hence $5^{2^x}=17k+1$.

Third, prove that this is true for $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$

We've shown that $5^{2^{x+1}}=17(k^2+2k)+1$, hence $5^{2^{x+1}}\equiv1\pmod{17}$.

---

Please note that the assumption is used only in the part marked red.

Answer 2

HINT: $\phi(17) = 16$ divides $2^x$ for $x>3$ , where $\phi$ is the Euler Totient Function.

Answer 3

The Fermat-Euler Theorem

If $\gcd(a,m)=1$, and let $\varphi(x)$ denote the Euler's function, then $$a^{\varphi(m)}\equiv1\pmod m.$$

Now set $m=17$ and $a=5$.

Answer 4

Hint: induction step $$ 5^{(2^{x+1})}=5^{2^x+2^x}=5^{2^x}\times5^{2^x}\equiv1\times 1\pmod{17}. $$

Answer 5

What you are performing is in fact "continued exponentiation". This can be seen from the equation $5 ^{2^x} = ((5 \overbrace{^2)^2)\ldots}^{\text{x times}} )^2$. So it is to be expected that once we reach $1$ the result remains $1^2=1$. In general using other base numbers than $5$, other exponents than $2$ and other moduli than $17$ yields beautiful snowflake-like graphs, see contexp.pdf.

Answer 6

${\rm mod}\ 17\!:\ \ \underbrace{\color{#c00}{5^{\large 16}}\equiv \color{#c00}{\bf 1}}_{\rm\large Fermat}\,\Rightarrow\, 5^{\large 2^{\Large 4+N}}\!\!\equiv (\color{#c00}{5^{\large 16}})^{\large 2^{\Large N}}\!\!\equiv {\bf\color{#c00}1}^{\large 2^{\large N}}\!\equiv 1 $