Exercise 2.4.4 ($561$ is not a strong pseudoprime to the base $2$)

Question

Show that the Carmichael number $561$ is composite by showing that it is not a spsp($2$).

Richard Ganaye · Accepted Answer

\begin{proof}
Using fast exponentiation, we obtain
$$2 ^{560} \equiv 1 \pmod{561},\qquad  2^{280} \equiv 1  \pmod{561},\ 	ext{ but }\ 2^{140} \equiv 63 
ot \equiv \pm 1 \pmod{561}.$$
This show that $561$ is not a spsp($2$), so $561$ is composite.
\end{proof}

Exercise 2.4.4 ($561$ is not a strong pseudoprime to the base $2$)

Answers

Comments

Exercise 2.4.4 ($561$ is not a strong pseudoprime to the base $2$)

Answers

Comments

Add answer