Show that : $a^{2^n} \equiv 1 \pmod {2^{n+2}}$ for all odd integers.
The question states to show that all odd integers satisfy the 3 congruence:
1. $a^4 \equiv 1 \pmod{16}$
2. $a^8 \equiv 1 \pmod{32}$
3. $a^{16} \equiv 1 \pmod{64}$
and then to show that in general, the main question is satisfied.
It is obvious that induction is implied for the main question, with (weak) type needed.
I am attempting these 3 :
1. Let, $a=2k+1, \exists k \in \mathbb{Z}$.
For (1), $a^4 = (2k+1)^4 = 16k^4 + 32k^3 +24k^2 +8k+1$
Taking out $1$ to the l.h.s., we get:
$a^4 - 1= 8k(2k^3 + 4k^2 +3k +1)$
It is obvious that am unable to show common factor as 16.
I will attempt rest once am clear what is wrong in the first one.
Based on inputs, have got formula amended for factoring out $16$, as: $16k(k^3 + 2k^2 +k) + 16\cdot C(k+1,2)$,
as $16\cdot C(k+1,2) \implies 8(k+1)k \implies 8k^2 + 8k$
For, the second case:
2. $a^8 \equiv 1 \pmod{32}$
$(2k+1)^8 = 2^8k^8 + 8\cdot2^7k^7 +28\cdot2^6k^6 + 56\cdot2^5k^5 + 70\cdot 2^4k^4 + 56\cdot2^3k^3 + 28\cdot2^2k^2 + 8\cdot2k + 1$
=> $(2k+1)^8 - 1 = 2^5(2^3\cdot k^8 + 2^5\cdot k^7 +56\cdot k^6 + 56\cdot k^5 + 35\cdot k^4 + 14\cdot k^3) + 112k^2 + 16k$
Am stuck again, as do not know how to find a suitable formula that gels with the earlier case's. It should yield 3 terms, after taking in $16$ as common factor:
=> $16(x\cdot k^3 + 7\cdot k^2 + k)$,
where $x$ should resemble earlier case, and so $x=16$.
This leads to :
=> $(2k+1)^8 - 1 = 2^5(2^3\cdot k^8 + 2^5\cdot k^7 +56\cdot k^6 + 56\cdot k^5 + 35\cdot k^4 + 6\cdot k^3) + ( 256k^3 + 112k^2 + 16k)$
$(256k^3 + 112k^2 + 16k) = 16(16k^3 + 7k^2 + k)$
Am stuck again, as have no such formula in mind.
Based on a great answer by @Szeto, have got a different approach that considers the modified-residue (which is: residue $-1 \equiv 0\pmod {32}$) only, and then proves that $32$ must be a factor of residue.
The modified-residue is given by : $256k^3 + 112k^2 + 16k$, and in fact there is no need to take out $256k^3$ from its earlier grouping, as the job can be done by the : $112k^2 + 16k$ part only.
=> $16k(7k + 1)$, where it can be shown that $k(7k+1)$ is always divisible by 2 for any integer (odd, or even) $k$.
Hence, proved for case 2.
For, the third case:
3. $a^{16} \equiv 1 \pmod{64}$
will ignore terms with the powers of $2k \ge 5$, and see how more trimming of expressions can be done:
Answer by @Szebo has shown how to use the result of case (2) for case (3).
Here I will do(part of) the proof of the general statement by M.I.:
Suppose when $n=k$(odd) the following is true for all odd $a$: $$a^{2^k} \equiv 1\pmod{2^{k+2}}$$
Then, for some integer $c$, $$a^{2^k} = c*2^{k+2} + 1$$.
When $n=k+2$, LHS = $$a^{2^{k+2}} = a^{2^k*4} = {a^{2^k}}^4 = (c*2^{k+2} + 1)^4$$.
And this can be expanded to: $$=c^4 2^{4k+8} + 4c^3 2^{3k+6} + 6c^2 2^{2k+4} + 4c 2^{k+2} +1$$
All terms except the last one are divisible by $2^{k+4}$. Note that the second last term is indeed divisible by $2^{k+4}$ since $4c 2^{k+2} = c 2^{k+4}$.
Thus the remainder is $1$ as expected.
You still need to prove that when $n=1$ the general statement is true for all odd $a$. That could be done easily by M.I.. ———————————-
In case (2), as the OP has derived, $$(2k+1)^8 \equiv 256k^3+112k^2+16k+1\pmod{32}$$.
Obviously, $256k^3$ is divisible by 32. So (the part of interest of) the original expression is reduced to: $$112k^2+16k=2^4(k)(7k+1)$$.
Obviously, as long as $k(7k+1)$ is even, the above expression is divisible by $32=2^5$.
When $k$ is odd, $7k+1$ is even, and the product of them is even as well. When $k$ is even, $k(7k+1)$ is even as well. Therefore, $k(7k+1)$ is always even.
As a result $2^4(k)(7k+1)$ is always divisible by 32.
Thus, $$(2k+1)^8 \equiv 1\pmod{32}$$
For case (3), there is a shortcut that avoids binomial expansion.
As we have proven the above result, we can write down for integer $b$: $$a^8=32b+1$$.
Therefore, $$a^{16}=(a^8)^2=(32b+1)^2=32^2b^2+64b+1\equiv 1\pmod{64}$$ as expected.
This indeed implies that case (2) can be proven similarly by using the result of case (1).