Prove that if $2^p− 1$ is composite where $p$ is prime then $2^p− 1$ is a base 2-pseudoprime.
The integer $2^p-1$ is a base 2 pseudoprime if both of the following are true
- $2^p-1$ is composite
- $2^{2^p-2} \equiv 1 \pmod {2^p-1}$ for $\gcd(2,2^p-1)=1$
We're given that $2^p-1$ is composite, so we only need to show the second condition.
We first note that $p=2$ is excluded by the antecedent of the statement we want to prove, since $2^2-1=3$ which is not composite. So we only consider $p>2$.
By FlT we have, noting $p \not \mid 2$ since $p>2$,
$$ \begin{align} 2^{p-1} & \equiv 1 \pmod p \\ \\ 2^{p} & \equiv 2 \pmod p \end{align}$$
This means, for some integer $k$, we have $2^p-2=kp$.
Noting that $2^p \equiv 1 \pmod {2^p-1}$, we have
$$ \begin{align} 2^{2^p-2} & \equiv 2^{kp} \pmod {2^p-1} \\ \\ & \equiv (2^p)^k \pmod{2^p-1} \\ \\ & \equiv (1)^k \pmod {2^p-1} \\ \\ & \equiv 1 \pmod {2^p-1}\end{align}$$
By showing that $2^p-1$ is composite, and that $2^{2^p-2} \equiv 1 \pmod {2^p-1}$, we have proved that if that if $2^p− 1$ is composite where $p$ is prime then $2^p− 1$ is a base 2-pseudoprime.