Prove $ 4\times 2^n $ divides $ a^{2^n}-1 $ for all odd a, and $ n \in \Bbb N $

Question

So I'm pretty sure this is an induction problem. I've got as far as expressing $ a=2k+1 $ , proving this for the base case $ n=1 $ , but I've then got stuck on the inductive step.

I've assumed $$ 2^{m+2} | (k-1)^{2^m} -1 $$

And then I've tried to perform induction on n: $$ (k-1)^{2^{m+1}} = (k-1)^{2^m} \times (k-1)^{2^m} -1 $$

But I'm not sure where to go from here, and whether I've actually done everything right so far. How would one prove the original statement?

Also apologies for bad formatting, I'm somewhat new to latex. Also apologies for bad formality in my attempted proof, I'm learning how to write proofs more formally, but I'm not there yet.

Answer 1

Induction on $\;n\;$ : assuming $\;2^{n+2}\,\mid\,(a^{2^n}-1)\;$, we now prove that $\;2^{n+3}\,\mid\,(a^{2^{n+1}}-1)\;$. But (Leo's comment is right on the money)

$$a^{2^{n+1}}-1=\left(a^{2^n}-1\right)\left(a^{2^n}+1\right)$$

Now, $\;2^{n+2}\;$ already divides the first factor on the right side, and the second one is even, so...

Answer 2

We can write, $a^{2^n}-1=(a^{2^{n-1}}+1)(a^{2^{n-2}}+1)...(a+1)(a-1).$

Now observe that there are $2^{n+1}$ factors above. As $a$ is odd, any one of $a+1$ or $a-1$ is divisible by 4 and the rest $2^n$ factors are all even for the same reason. Thus, their product is divisible by $4 \times 2^n.$