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?

  • $\begingroup$ 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. $\endgroup$ – 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)$$

  • $\begingroup$ At each stage, you multiply by a number with a single factor of $2$. $\endgroup$ – Empy2 Jan 14 '15 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.