Exercise 2.4.20* (Carmichael numbers)

Proof.

a)

Using $p_1\equiv 1(\mathit{mod}{p}_1-1)$, and $p_1-1=6k$, we obtain $$\begin{array}{llll}\hfill m-1& \equiv p_2{p}_3-1(\mathit{mod}{p}_1-1),& \hfill & \\ \hfill p_2{p}_3-1& =(12k+1)(18k+1)-1& \hfill & \\ \hfill & =216k^2+30k& \hfill & \\ \hfill & =6k(36k+5)& \hfill & \\ \hfill & \equiv 0(\mathit{mod}{p}_1-1),& \hfill & \end{array}$$

so

$$p_1-1\mid m-1.$$

Similarly, with $p_2-1=12k$,

$$\begin{array}{llll}\hfill m-1& \equiv p_1{p}_3-1,& \hfill & \\ \hfill p_1{p}_3-1& =(6k+1)(18k+1)-1& \hfill & \\ \hfill & =108k^2+24k& \hfill & \\ \hfill & =12k(9k+2)& \hfill & \\ \hfill & \equiv 0(\mathit{mod}{p}_2-1),& \hfill & \end{array}$$

so

$$p_2-1\mid m-1.$$

Finally, with $p_3-1=18k$,

$$\begin{array}{llll}\hfill m-1& \equiv p_1{p}_2-1(\mathit{mod}{p}_3-1)& \hfill & \\ \hfill p_1{p}_2-1& =(6k+1)(12k+1)-1& \hfill & \\ \hfill & =72k^2+18k& \hfill & \\ \hfill & =18k(4k+1)& \hfill & \\ \hfill & \equiv 0(\mathit{mod}{p}_3-1)& \hfill & \end{array}$$

so

$$p_3-1\mid m-1.$$

b)

Suppose that $a\wedge m=1$. Then $a\wedge p_i=1$, for $i=1,2,3$. By Fermat theorem, $$a^{p_i-1}\equiv 1(\mathit{mod}{p}_i),i=1,2,3.$$

Since $p_i-1\mid m-1$, we have

$$a^{m-1}\equiv 1(\mathit{mod}{p}_i),i=1,2,3.$$

Since $p_1,p_2,p_3$ are distinct primes, therefore relatively prime by pairs, $a^{m-1}\equiv 1(\mathit{mod}{p}_1{p}_2{p}_3)$, that is

$$a^{m-1}\equiv 1(\mathit{mod}m)$$

for all integer $a$ prime to $m$, so the composite $m=p_1{p}_2{p}_3$ is a Carmichael number.