# Show that if $n>1$ then $3^{2^{n}} = 1 + q_{n}2^{n+2}$ for some odd integer $q_{n}$

So basically we have to show that:

$3^{2^{n}} \equiv 1$ mod $(q_{n}2^{n+2})$ for some odd integer $q_{n}$

Using Eulers theorem we can rewrite this question as:

Show $\varphi (q_{n}2^{n+2}) = 2^{n}$ for some odd integer $q_{n}$

So I replace $q_{n}$ with $(2k-1)$ for some $k \in \mathbb{Z}$

I've gone down this route and haven't figured it out. Any ideas? Am I on the right track?

• Rewriting would mean that the two questions are equivalent. Euler's theorem is not an if-and-only-if, so you could say that "it is enough to show that" but not "we can rewrite this question as". In fact, it is not at all true that $\phi(q_n 2^{n+2}) = 2^n$ for any integer $q_n$: Euler's theorem isn't strong enough to prove this claim, so you need to try a different route. – Erick Wong Jan 14 '15 at 14:53

Hint: $$3^{2^{n+1}}-1=3^{2^n2}-1=(3^{2^n})^2-1\\=(3^{2^n}-1)(3^{2^n}+1)$$
• At each stage, you multiply by a number with a single factor of $2$. – Empy2 Jan 14 '15 at 14:51