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

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.

• Where did you show that $a^4\equiv 1\bmod 16$? Commented May 1, 2022 at 15:57
• I just edited. I didn't feel like that part was important to show Commented May 1, 2022 at 16:08
• Do you know there is an explicit formula for $\phi(2^n)$?
– D_S
Commented May 1, 2022 at 16:09
• The base case $n=4$ is still important and you should finish the solution there. Why is $16k^4+32k^3+24k^2+8k+1$ congruent to $1$ modulo $16$? And indeed, the induction step becomes trivial if you write down the formula for $\phi(2^n)$. Commented May 1, 2022 at 16:10
• Oh I think I see now. $$\phi(2^n) = 2^n - 2^{n-1}$$. So then $$\phi(2^{n+1}) = 2^{n+1} - 2^{n}$$ Commented May 1, 2022 at 16:19

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?