Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
3  
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. –  Andres 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
1  
@Andres: ... and it was after 1am at the time. (-; –  Arturo Magidin Feb 17 '11 at 16:03
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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