Exercise 2.1.54 (Pseudoprimes and Carmichael numbers)

Proof.

a)

Since $2^5=32\equiv 1(\mathit{mod}31)$, then $2^{340}={(2^5)}^{6}8\equiv 1(\mathit{mod}31)$, thus $$2^{341}\equiv 2(\mathit{mod}31).$$

Similarly, $2^5\equiv -1(\mathit{mod}11)$, thus $2^{10}\equiv 1(\mathit{mod}11)$, then $2^{340}={(2^{10})}^{34}\equiv 1(\mathit{mod}11)$, thus

$$2^{341}\equiv 2(\mathit{mod}11).$$

Using $31\mid 2^{341}-2$, and $11\mid 2^{341}-2$, where $31\wedge 11=1$, we obtain $31\cdot 11\mid 2^{341}-2$, so

$$2^{341}\equiv 2(\mathit{mod}341).$$

(But $3^{341}\equiv 168\not\equiv 3(\mathit{mod}341)$.)

So $341=11\cdot 31$ is a pseudo-prime to the base $2$.

b)

• If $a\equiv 0(\mathit{mod}3)$, $a^{561}\equiv a\equiv 0(\mathit{mod}3)$.

  If not, $a^2\equiv 1(\mathit{mod}3)$ (Fermat’s theorem), and $2\mid 560$, thus $a^{560}\equiv 1(\mathit{mod}3)$, therefore

  $$a^{561}\equiv a(\mathit{mod}3).$$

• If $a\equiv 0(\mathit{mod}1)1$, $a^{561}\equiv a\equiv 0(\mathit{mod}11)$.

  If not, $a^{10}\equiv 1(\mathit{mod}11)$ (Fermat’s theorem), and $10\mid 560$, thus $a^{560}\equiv 1(\mathit{mod}11)$, therefore

  $$a^{561}\equiv a(\mathit{mod}11).$$

• If $a\equiv 0(\mathit{mod}1)7$, $a^{561}\equiv a\equiv 0(\mathit{mod}17)$.

  If not, $a^{16}\equiv 1(\mathit{mod}17)$ (Fermat’s theorem), and $16\mid 560=16\times 35$, thus $a^{560}\equiv 1(\mathit{mod}17)$, therefore

  $$a^{561}\equiv a(\mathit{mod}17).$$

Since $3,11,17$ are relatively prime in pairs, $3\cdot 11\cdot 17\mid a^{561}-a$, so

$$\forall <!--\; FUNCTION\; APPLICATION\; -->a\in \mathbb{Z},a^{561}\equiv a(\mathit{mod}561).$$

The composite integer $561$ is a Carmichael number.