Show that if the Fermat number $F_n = 2^{2^n} + 1$ is a composite integer then $F_n = 2^{2^n} + 1$ is a base 2-pseudoprime.
To show that $F_n$ is a base 2 pseudoprime, we need to show
- $F_n$ is composite
- $2^{F_n-1} \equiv 1 \pmod {F_n}$
We are assuming $F_n$ is composite.
By definition $F_n \equiv 0 \pmod {F_n}$, that is, $2^{2^n}+1 \equiv 0 \pmod {2^{2^n}+1}$. And so
$$ 2^{2^n} \equiv -1 \pmod {F_n} $$
Can we raise $2^{2^n}$ to a power $k$ such that the result is $2^{F_n-1} = 2^{2^{2^n}}$ ?
$$ \begin{align} (2^{2^n})^k & = 2^{2^{2^n}} \\ \\ 2^{k \times 2^n} & = 2^{2^{2^n}} \\ \\ k \times 2^n & = 2^{2^n} \\ \\ k & = 2^{(2^n-n)} \end{align} $$
And so, using Proposition (3.8) that $a \equiv b \pmod n \implies a^m \equiv b^m \pmod n $, for natural $m$, we have
$$ \begin{align} 2^{2^n} & \equiv -1 \pmod {F_n} \\ \\ (2^{2^n})^k & \equiv (-1)^k \pmod {F_n} \\ \\ 2^{F_n-1} & \equiv (-1)^{2^{(2^n-n)}} \pmod {F_n} \\ \\ & \equiv 1 \pmod {F_n} \end{align} $$
We have shown that $2^{F_n-1} \equiv 1 \pmod {F_n}$, which means $F_n$ is a base 2 pseudoprime, if $F_n$ is composite.