# Show that all Fermat numbers pass the base $2$ test (pseudoprime).

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.

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

## 1 Answer

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.