Exercise 2.4.7 (Old pseudoprimes to base $a$)

Question

Some earlier authors called a composite number $m$ a pseudoprime to the base $a$ if $a^m \equiv a \pmod m$. To distinguish this definition from the one we adopted (at the end of Section 2.1), call such a number $m$ an {\bf old pseudoprime to base $a$}. Explain why the set of pseudoprimes to base $a$ lies in the set of old pseudoprimes to base $a$. Demonstrate that the two definitions do not coincide by showing that $m = 161,038$ is an old pseudoprime to base $2$, but not a pseudoprime to base $2$

Richard Ganaye · Accepted Answer

\begin{proof}
Let $m$ be a composite number.

If $a^{m-1} \equiv 1 \pmod m$, then , multiplying by $a$, we obtain $a^m \equiv a \pmod m$. This shows that the set of pseudoprimes to base $a$ lies in the set of old pseudoprimes to base $a$.

If $m = 161,038$, then $a^m \equiv a \pmod m$, but $a^{m-1} \equiv 80520 \pmod m$, so $m = 161,038$ is an old pseudoprime to base $2$, but not a pseudoprime to base $2$.
\end{proof}

Exercise 2.4.7 (Old pseudoprimes to base $a$)

Answers

Comments

Exercise 2.4.7 (Old pseudoprimes to base $a$)

Answers

Comments

Add answer