Proving $a^{\phi(2^n)/2} \equiv 1 \bmod 2^n$, where $\phi$ is Euler's Phi Function

Question

Here is the problem Let $a$ be and odd number and let $n$ be an integer greater than $3$. Let $\phi$ be the Euler Phi Function.

Prove that $$a^{\phi(2^n)/2} \equiv 1 \bmod 2^n$$ Use induction on $n$.

So far I have

Proof is by induction. Let $n = 4$ $$a^{\phi(2^n)/2} = a^{8/2} = a^{4}$$ Let $a = 2k+1$ where $k$ is a positive integer. Now $$a^4 \equiv (2k+1)^4 = 16k^4 + 32k^3 +24k^2 + 8k + 1 \equiv 1\bmod 16$$ Now let $ a^{\phi(2^m)/2} \equiv 1 mod 2^m $ be true for some m. We need to show $a^{\phi(2^{m+1})/2} \equiv 1 \bmod 2^{m+1}$ holds. Update: $$a^{\phi(2^{{m+1}})/2} \equiv a^{(2^{m+1}-2^{m})/2} \equiv a^{2(2^{m} - 2^{m-1})/2} \equiv a^{2\phi(2^{m})/2}$$ Now from here I am kind of lost I know for all integers greater than or equal to $3$ we have that $\phi(n)$ is odd. I also have Euler's theorem. I felt like I could use Euler's theorem since $a^{\phi(2^n)/2}$ is odd and $2^n$ is always even. But wouldn't that get rid of the use of induction? I think I may have something fundamental missing but I am not too sure. Any help would be grateful.

Answer 1

Since $\varphi(2^n) = 2^n-2^{n-1} = 2^{n-1},$ it suffices to show: $$a^{2^{n-2}}\equiv 1\pmod{2^n}$$ for $n\geq 3. $ All you need for this is the formula $x^2-y^2 = (x-y)(x+y)$ and induction. You just need to smartly choose $x$ and $y$ here. Can you how this can play out?