2.4: Problem 2: Show that \(2^{45} \equiv 57 \pmod{91}\). Deduce that \(91\) is composite.
Proof
We can show that \(2^{45} \equiv 57 \pmod{91}\) by fast exponentiation as follows
$$
\begin{align*}
2^4 &\equiv 16 \pmod{91} \\
2^7 &\equiv 128 \equiv 37 \pmod{91} \\
2^{14} &\equiv 37^2 \equiv 4 \pmod{91} \\
2^{28} &\equiv (2^{14})^2 \equiv 4^2 \equiv 16 \pmod{91} \\
2^{42} &\equiv (2^{14})^3 \equiv 4^3 \equiv 64 \pmod{91} \\
2^{45} &\equiv 2^{42} \cdot 2^3 \equiv 64 \cdot 8 \equiv 57 \equiv 19 \cdot 3 \pmod{91} \\
\end{align*}
$$
Observe now that
$$
\begin{align*}
2^{45} &\equiv 57 \pmod{91} \\
2^{90} &\equiv (2^{45})^2 \equiv 64 \pmod{91}
\end{align*}
$$
However by Fermat’s theorem, since \((91,2) = 1\) and if \(91\) was prime, then we would expect
$$
\begin{align*}
2^{90} \equiv 1 \pmod{91} \\
\end{align*}
$$
This implies that \(91\) is not prime as we wanted to show. \(\blacksquare\)