Proving that $2^{n+2} \mid a^{2^{\large{n}}} - 1 $, for $a \in \mathbb{Z}$ odd, $n \in \mathbb{N}$ How can I prove this? I was thinking of using strong induction on $n$, and I've managed to prove the base case using induction again on $a$,
$$2^3 \mid a^{2} - 1$$
but I couldn't work my way around the rest of the proof with the usual properties of divisibility (if $m \mid n$, then $a^m - 1 \mid a^n - 1$, etc). 
 A: Hint: 
$$
a^{2^n} - 1 = (a^{2^{n-1}} - 1)(a^{2^{n-1}} + 1)
$$
A: Hint
If $t_m=a^{2^m}=1+b2^r,$. where $b,r$ are non-negative integers and $b$ is odd
$t_{m+1}=(1+b2^r)^2=1+b2^{r+1}(1+b2^{r-1})$
If $r-1>0,$ the highest power of $2$ that divides $t_{m+1}$ is $r+1$
$m=1\implies a^2=(2c+1)^2=8\cdot\dfrac{c(c+1)}2+1$ as $a$ is odd,$a=2c+1$(say)
$\implies2^3$ divides $a^2-1$
So, by induction the proposition can be established
A: Induction.
The base case $n = 1$ reads
$2^3 \mid a^2 - 1; \tag 1$
this holds since, $a$ being odd, $a - 1$ and $a + 1$ are both even; since $a \pm 1$ are consecutive even integers, each is divisible by $2$ and one is divisible by $4 = 2^2$; this establishes (1).
We hypothesize
$2^{k + 2} \mid a^{2^k} - 1; \tag 2$
we have
$a^{2^{k + 1}} - 1 = (a^{2^k} - 1)(a^{2^k} + 1); \tag 3$
we also have
$2 \mid a^{2^k} + 1, \tag 4$
since $a$ is odd, implying $a^{2^k}$ is also odd; (2) and (4) imply
$\exists c, d \in \Bbb Z, \; 2^{k + 2}c = a^{2^k} - 1, \; 2d = a^{2^k} + 1; \tag 5$
thus, via (3),
$2^{(k + 1) + 2}cd = 2^{(k + 2) + 1}cd =(2^{k + 2}c)(2d) = (a^{2^k} - 1)(a^{2^k} + 1) = a^{2^{k + 1}} - 1; \tag 6$
and thus,
$2^{(k + 1) + 2} \mid a^{2^{k + 1}} - 1, \tag 7$
completing the induction and proving that
$2^{n + 2} \mid a^{2^n} - 1, \; \forall n \in \Bbb N. \tag 8$
A: Let $\phi$ denote the Euler's totient function and by Euler's theorem we know that $$ a^{\phi(2^{n+2})}\equiv 1\pmod{2^{n+2}} $$
By the definition of Euler's totient fucntion we know that $$ \phi(2^{n+2})=2^{n+2}-2^{n+1}=2^{n+1} $$
so $$ (a^{2^{n}})^2\equiv 1\pmod{2^{n+2}} .$$
And we conclude that $$ a^{2^n}\equiv 1 \pmod{2^{n+2}} $$ since otherwise, $a$ would be either a primitive root mod $2^{n+2}$ contradicting the fact that No primitive root modulo $2^n$ for $n≥3$, or $ a^{2^k}\equiv1 $ for some $k\le n-1$, but then $a^{2^n}$ would be congrunt to $1$ mod $2^{n+2}$ too. Contradiction!
