How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

Question

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a total nonsense, but i'm new to modular arithmetic, so i might be wrong!

I tried by induction, but i really failed here and turned out i showed that $$3^{2^{2k+1}} \equiv 1 (mod \ 2^{k+2})$$, so that isn't helpful.

I tried to work with eulers theorem and i got $$3^{\varphi(2^{k+2})} \equiv 1 (mod \ 2^{k+2}) \Leftrightarrow 3^{2^{k+1}} \equiv 1 (mod \ 2^{k+2})$$ but i wanted to show $$3^{2^k} \equiv 1 (mod \ 2^{k+2})$$

I'd really love to get some hints! Cheers

Answer 1

(This is not much more than a reformulation of Nishant's comment). Let $v_2(n)$ denote the highest power of $2$ dividing $n$, so $2^{v(n)}\mid n$ and $2^{v(n)+1}\not\mid n$. Then

• If $m$ is even, we have $v_2(3^m-1)=v_2((3^{m/2}-1)(3^{m/2}+1))=v_2(3^{m/2}-1)+v_2(3^{m/2}+1)$
• If $m$ is even, we have $v_2(3^m+1)=1$ because $3^m\equiv 1\pmod 4$
• If $m$ is odd, then $v(3^m-1)=1$ because $3^m\equiv -1\pmod 4$
• $v(3^1+1)=2$ (we do not need an explicit result for the general case $v(3^m+1)$ with $m$ odd

With this, you can show your conjecture $$v(3^{2^k}-1)=k+2$$ by induction for $k\ge1$. (Warning: For $k=0$, we have $v(3^{2^k}-1)=k+1$).