(a) Show that 561 is a
(i) base 560-pseudoprime
(ii) base 562-pseudoprime
(b) Show that 91 is not a base2-pseudoprime.
(a)
(i) To show 561 is a base 560 pseudoprime, we need to show both
- 561 is composite
- $560^{561-1} \equiv 1 \pmod {561}$
561 is composite since $561 = 3 \times 11 \times 17$.
Also, noting $560 \equiv -1 \pmod {561}$
$$ \begin{align} 560^{561-1} & \equiv (-1)^{560} \pmod {561} \\ \\ & \equiv 1 \pmod {561} \end{align} $$
And so 561 is a base 560 pseudoprime.
(ii) To show 561 is a base 562 pseudoprime, we need to show both
- 561 is composite
- $562^{561-1} \equiv 1 \pmod {561}$
561 is composite since $561 = 3 \times 11 \times 17$.
Also, noting $562 \equiv 1 \pmod {561}$
$$ \begin{align} 562^{561-1} & \equiv (1)^{560} \pmod {561} \\ \\ & \equiv 1 \pmod {561} \end{align} $$
And so 562 is a base 560 pseudoprime.
(b) To show 91 is not a base 2 pseudoprime we need to at least one of
- 91 is prime
- $2^{91-1} \not \equiv 1 \pmod {91}$
Since $91=7 \times 13$, it is not prime. So we need to show $2^{91-1} \not \equiv 1 \pmod {91}$.
Noting that $2^{12}\equiv 4096 \equiv 1 \pmod {91}$, we have
$$ \begin{align} 2^{91-1} \equiv (2^{12})^7 \times 2^{6} \pmod{91} \\ \\ & \equiv 64 \pmod {91} \\ \\ & \not \equiv 1 \pmod {91} \end {align} $$
And so 91 is not a base 2 pseudoprime.