1
$\begingroup$

I realize that there is a similar post to this, but that post included a hint which we were not given. Also regarding that hint, I'm just wondering how someone could find it out for themselves. Here is the related post:

Show that every composite Fermat number is a pseudoprime base 2.

I know that $F_n = 2^{2^n} + 1$ and therefore $\,2^{2^n} \equiv -1 \pmod{F_n}$.

But I don't intuitively know the next step to take to show that $\ 2^{F_n}\equiv 2\pmod{\!F_n},\,$ i.e. that $$2^{2^{2^n} + 1} \equiv 2 \pmod{2^{2^n}+1}$$

So in essence, I would like to know how to solve it without knowing the hint. Thank you.

$\endgroup$
1
  • $\begingroup$ You need to take it $\mod 2^{2^n}+1$, not $\mod 2^{2^n}$ $\endgroup$ – vrugtehagel Mar 21 '18 at 18:02
1
$\begingroup$

We need to prove $$2^{2^{2^n}+1}\equiv 2 \mod 2^{2^n}+1$$

See that $2^{2^n}\equiv -1\mod 2^{2^n}+1$, and raising both sides to the power $2^{2^n-n}$, we see

$$(2^{2^n})^{2^{2^n-n}}\equiv 1\mod 2^{2^n}+1$$

and so

$$2^{2^n\cdot2^{2^n-n}}\equiv 2^{2^{2^n}}\equiv 1\mod 2^{2^n}+1$$

Now multiply by $2$ and we're done.

$\endgroup$

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.