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?


  • 1
    $\begingroup$ 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$ $\endgroup$ – 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.

  • 4
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Feb 17 '11 at 7:35
  • $\begingroup$ @Andres: Yes; I mentioned the CRT argument because it's a very common argument that shows up a lot as well. $\endgroup$ – Arturo Magidin Feb 17 '11 at 14:12
  • 1
    $\begingroup$ @Andres: ... and it was after 1am at the time. (-; $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.