Sunday, 18 January 2026

Exercise (4.3).12

Show that 1729 is a Carmichael number.


Let's remind ourselves of Definition (4.14). 

A composite integer $n$ is called a Carmichael number if for every base $a^{n−1} \equiv 1 \pmod n$ provided $\gcd (a, n) = 1$.


We start with the prime decomposition $1729 = 7 \times 13 \times 19$, which also tells us 1729 is composite.

Using FlT we have

$ a^{7-1} \equiv 1 \pmod {7}$ for $\gcd(a,7)=1$

$ a^{13-1} \equiv 1 \pmod {13}$ for $\gcd(a,7)=1$

$ a^{19-1} \equiv 1 \pmod {19}$ for $\gcd(a,7)=1$


We then note

$ a^{1728} \equiv (a^6)^{288} \equiv (1)^{288} \equiv 1 \pmod {7}$ for $\gcd(a,7)=1$

$ a^{1728} \equiv (a^12)^{144} \equiv (1)^{144} \equiv 1 \pmod {13}$ for $\gcd(a,13)=1$

$ a^{1728} \equiv (a^18)^{96} \equiv (1)^{96} \equiv 1 \pmod {17}$ for $\gcd(a,19)=1$


We can then use the result of Ex (3.4)8b to combine these

$$ \begin{align} a^{1729-1} & \equiv 1 \pmod {7 \times 13 \times 19} \\ \\ a^{1729-1} & \equiv 1 \pmod {1729} \end{align}$$


So we have shown that 1729 is composite, and also that $a^{1729-1} \equiv 1 \pmod {1729}$ for all $a$ where $\gcd(a,1729)=1$. And so 1729 is a Carmichael number.