Show that 2047 is a base 2-pseudoprime.
To show that a number $n$ is a base $b$-pseudoprime, where $b>1$ and $\gcd(b,n)=1$, we need to show both
- $n$ is composite
- $b^{n-1} \equiv 1 \pmod n$
$2047 = 23 \times 89$ and so is composite.
We now show $2^{2047-1} \equiv 1 \pmod {2047}$. We note that $2^{11} \equiv 2048 \equiv 1 \pmod {2047}$.
$$ \begin{align} 2^{2047-1} & \equiv 2^{2046} \pmod {2047} \\ \\ & \equiv (2^{11})^{186} \pmod {2047} \\ \\ & \equiv (1)^{186} \pmod {2047} \\ \\ & \equiv 1 \pmod {2047} \end{align} $$
We've shown $2^{2047-1} \equiv 1 \pmod {2047}$ and yet 2047 is composite, and so 2047 is a base 2-pseudoprime.