Prove Proposition (4.13).
Proposition (4.13) says that if $n$ is a base 2-pseudoprime then $2^n− 1$ is also a base 2-pseudoprime.
We start by assuming that $n$ is a base 2-pseudoprime. This means that both of the following are true
- $n$ is composite
- $2^{n-1} \equiv 1 \pmod n$
We need to show both
- $2^n-1$ is composite
- $2^{(2^n-2)} \equiv 1 \pmod {2^n-1}$
Since $n$ is composite, Corollary (4.11) which we proved in the previous exercise, tells us that $2^n-1$ is composite.
We know $2^{n-1} \equiv 1 \pmod n$, and so $2^n \equiv 2 \pmod n$, which means for some integer $k$, we have $2^n-2 = kn$.
$$ \begin{align} 2^{(2^n-2)} & \equiv 2^{kn} \pmod {2^n-1} \\ \\ & \equiv (2^n)^k \pmod {2^n-1} \\ \\ & \equiv (1)^k \pmod {2^n-1} \\ \\ & \equiv 1 \pmod {2^n-1} \end{align} $$
We have shown $2^{2^n-2} \equiv 1 \pmod {2^n-1}$.
And so if $n$ is a base 2-pseudoprime then $2^n− 1$ is also a base 2-pseudoprime.