(a) Show that 25 is a base 7-pseudoprime but not a Carmichael number.
(b) Show that 217 is a base 5-pseudoprime but not a Carmichael number.
(a) To show 25 us a base 7 pseudoprime but not a Carmichael number, we need to show:
- 25 is composite
- $7^{25-1} \equiv 1 \pmod {25}$
- A counterexample $x$ where $x^{25-1} \not \equiv 1 \pmod {25}$ where $\gcd(25,x)=1$
$25=5\times5$ and so 25 is composite.
Using $7^4 \equiv 2401 \equiv 1 \pmod {25}$, we have
$$ \begin{align} 7^{25-1} & \equiv (7^4)^6 \pmod {25} \\ \\ & \equiv 1^6 \pmod {25} \\ \\ & \equiv 1 \pmod{25} \end{align} $$
Using $x \equiv 3 \pmod{25}$, which is coprime to 25, we have $3^3 \equiv 2 \pmod {25}$, and so
$$ \begin{align} 3^{25-1} & \equiv (3^3)^8 \pmod {25} \\ \\ & \equiv 2^8 \pmod {25} \\ \\ & \equiv 6 \pmod{25} \\ \\ & \not \equiv 1 \pmod{25} \end{align} $$
And so 25 is a base 7 pseudoprime but not a Carmichael number.
(b) To show 217 us a base 5 pseudoprime but not a Carmichael number, we need to show:
- 217 is composite
- $5^{217-1} \equiv 1 \pmod {217}$
- A counterexample $x$ where $x^{217-1} \not \equiv 1 \pmod {217}$ where $\gcd(217,x)=1$
$217=7\times31$ and so 217 is composite.
Using $5^6 \equiv 15625 \equiv 1 \pmod {217}$, we have
$$ \begin{align} 5^{217-1} & \equiv (5^6)^{36} \pmod {217} \\ \\ & \equiv 1^{36} \pmod {217} \\ \\ & \equiv 1 \pmod{217} \end{align} $$
Using $x \equiv 4 \pmod{217}$, which is coprime to 217, we have $4^8 \equiv 2 \pmod {217}$, and so
$$ \begin{align} 4^{217-1} & \equiv (4^8)^{27} \pmod {217} \\ \\ & \equiv 2^{27} \pmod {217} \\ \\ & \equiv (2^3)^9 \pmod {217}\\ \\ & \equiv 190 \pmod{217} \\ \\ & \not \equiv 1 \pmod{217} \end{align} $$
And so 217 is a base 5 pseudoprime but not a Carmichael number.