A Carmichael number has at least 3 prime divisors

A few minutes ago I stumbled on the above result in the comment section of a blogpost of John Cook, and I naturally tried to prove it. Well, it´s not really a proof, you just have to make some educated guesses and see if they work. So that´s totally inside my comfort zone. Here is the result:

Let $pq$ be a Carmichael number, such that $p$ and $q$ are primes. Then we have the following $\pmod{pq}$ :

$1 \equiv p^{pq - 1} \equiv q^{pq - 1} \equiv 1 \equiv (p + q)^{pq - 1} \equiv p^{pq - 1} + q^{pq - 1} \equiv 1 + 1 \equiv 2$

Contradiction :).

EDIT: I am terribly sorry, but I made some huge, stupid mistakes here.
Mistake 1: A Carmichael number is a composite number $n$ such that, for every COPRIME $b$ , we have $b^{n-1} \equiv 1 \pmod{n}$ . If I assume $n = pq$ , I can’t say that $p^{n-1} \equiv 1 \pmod{n}$ , because $p$ and $pq$ are not coprime.
Mistake 2: I assumed $n = pq$ . Why may I assume that? The answer is that I just can’t! $n$ could very well be $pq^2$ , and still have less than 3 prime divisors.

Maybe my proof can be salvaged though.. Or maybe you just need Korselt’s criterion or something.

This entry was posted on October 14, 2010 at 15:47 and is filed under Problem Solving. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

8 Responses to “A Carmichael number has at least 3 prime divisors”

thomas Says:
October 14, 2010 at 16:42 | Reply
i dont understand why you do “(p + q)^…” instead of “(p * q)^…”, why the addition instead of the multiplication
- Woett Says:
  October 14, 2010 at 17:32 | Reply
  well, a Carmicheal number n is a number such that for ANY b (with b and n coprime) the equation b^(n-1) = 1 (mod n) is true. So if we find 1 value for b for which that equation doesn’t hold, we proved that n is NOT a Carmichael number. So in particular we should have that, if we assume pq is Carmicheal, that p^(pq – 1) = 1 (mod pq), but also that q^(pq – 1) = 1 (mod pq), but also, since it should hold for EVERY number b, (p + q)^(pq – 1) = 1 (mod pq). So in this case b = p + q. And in the above proof you see that if the first 2 of these have value 1, then (p + q)^(pq – 1) = 2 (mod pq), instead of 1 (mod pq)! So pq cannot be Carmichael.
  
  Hope this helped. Otherwise, please ask again!!
  - thomas Says:
    October 20, 2010 at 12:29 | Reply
    thanks for the explanation, appreciated. and sorry for my late reply…
    
    i did indeed overread the “ANY b” part. so i guess p + q is always coprime to q*p?
    
    where do you study, if you dont mind me asking?
    - Woett Says:
      October 20, 2010 at 16:04 | Reply
      If they weren’t coprime, they would have to share a common primedivisor. But the only primedivisors of pq are p and q. So if p divides p+q, it has to divide q as well, and since q is prime, this is not possible. And analagously, if q would divide p+q, it would have to divide p as well..
      
      I study at the University of Utrecht, in the Netherlands
Margriet Says:
October 15, 2010 at 17:39 | Reply
WOUTER!

Did I just find your blog?
Wow that’s great!!

Hilarische blog overigens. Ik heb gelijk weer memorabele herinneringen aan onze gezamenlijke Wis A1,2 klassen waarbij jij me allerlei dingen probeerde uit te leggen (er was een zo’n ding met pijlen ofzo dat ik nooit snapte, wat was dat ook alweer?)

Anyway: hoe is het met je en laten we in contact blijven! zou het echt superleuk vinden je tzt (als ik weer in den lande ben) je te zien.
- Woett Says:
  October 15, 2010 at 18:32 | Reply
  Pwoaaaaah! Grietje 🙂 Lang leve de kettingregel. Hier alles puik! Jij leuke verjaardag gehad vorige week? En had je m’n sms nog gekregen?
Supplements Site Says:
March 17, 2015 at 07:30 | Reply
Excess HGH based on info found at HGHhelp can lead to formation of tumors of the somatotroph cells of the anterior pituitary gland.
Arequirement for a healthy male reproductive system and sperm
re-production. The supplements add to the benefits of the fitness exercises.
Koiti Kimura (@koitiluv1842) Says:
October 24, 2021 at 08:32 | Reply

This book's "Chapter A13: Carmichael Numbers" says that there are an actually-infinite number of Carmichael numbers with k (such that k≧3) different prime factors: https://t.co/XISHcmXZ52

— Mr. Koiti Kimura (@koitiluv1842) October 24, 2021