# Verifying Carmichael numbers

I'm trying to understand a solution I was given in a tutorial regarding a problem with Carmichael numbers and I was wondering if you guys can help clarify things:

A composite number $m$ is called a Carmichael number if the congruence $a^{m-1} \equiv 1 \pmod{m}$ is true for every number a with $\gcd(a,m) = 1$.

Verify that $m = 561 = 3 \times 11 \times 17$ is a Carmichael number.

Solution given:

Apply Fermat's Little Theorem to each prime divisor of $m$: \begin{align*} a^2 &\equiv 1 \pmod{3}\\ a^{10} &\equiv 1 \pmod{11}\\ a^{16} &\equiv 1 \pmod{17} \end{align*} This somehow then implies that $a^{80} \equiv 1 \pmod{561}$ then accordingly $a^{560} \equiv 1 \pmod{561}$.

I am lost as to how the 3 congruences imply $a^{80} \equiv 1 \pmod{561}$ ($80 = \mathrm{LCM}(2,10,16)$).

Can somebody clarify this for me?

Thanks!

• for equivalence, use \equiv and put your $LaTeX$ in dollar signs. So you would write a^2 \equiv 1 \pmod 3 and get $a^2 \equiv 1 \pmod 3$ – Ross Millikan Feb 17 '11 at 15:33

Note that $80 = \mathrm{lcm}(2,10,16)$. So you can write $a^{80} = (a^2)^{40} = (a^{10})^{8} = (a^{16})^5$. So, \begin{align*} a^{80}= (a^2)^{40} &\equiv 1^{40} = 1\pmod{3},\\ a^{80}= (a^{10})^{8} &\equiv 1^8 = 1 \pmod{11},\\ a^{80}= (a^{16})^5 &\equiv 1^5 = 1\pmod{17}. \end{align*}

By the Chinese Remainder Theorem, the system of congruences \begin{align*} x&\equiv 1\pmod{3}\\ x&\equiv 1\pmod{11}\\ x&\equiv 1\pmod{17} \end{align*} has a unique solution modulo $3\times 11\times 17 = 561$. But both $x=1$ and $x=a^{80}$ are solutions. Since the solution is unique modulo $561$, then the two solutions we found must be congruent. That is, $$a^{80}\equiv 1\pmod{561}.$$

(Added. Or, more simply, as Andres points out, since $3$, $11$, and $17$ each divide $a^{80}-1$, and are pairwise relatively prime, then their product divides $a^{80}-1$).

Once you have that $a^{80}\equiv 1\pmod{561}$, then any power of $a^{80}$ is also congruent to $1$ modulo $561$. In particular, $$a^{560} = (a^{80})^{7} \equiv 1^7 = 1 \pmod{561}$$ as desired.

• Arturo, I think you can do this more easily: Simply note that since $a^{80}-1$ is divisible by 3, 11, and 17, and these numbers are relatively prime, then it is divisible by their product. There is no need to invoke the Chinese Remainder Theorem. – Andrés E. Caicedo Feb 17 '11 at 7:35
• @Andres: Yes; I mentioned the CRT argument because it's a very common argument that shows up a lot as well. – Arturo Magidin Feb 17 '11 at 14:12
• @Andres: ... and it was after 1am at the time. (-; – Arturo Magidin Feb 17 '11 at 16:03

HINT $\:$ For primes $\rm\ p\neq q\:$ coprime to $\rm\:a\:,\:$ if $\rm\ p-1,q-1\ |\ m\$ then $\rm\ p,q\ |\ a^m - 1\ \Rightarrow\ pq\ |\ a^m - 1$ since lcm = product for coprime integers (here distinct primes).

You will have to consider two cases though. Case 1 will be that $a$ is not relatively prime to $561$ and case two will be that $5$61 and $a$ are relatively prime.