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.

Advertisements

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

  1. thomas Says:

    i dont understand why you do “(p + q)^…” instead of “(p * q)^…”, why the addition instead of the multiplication

    • Woett Says:

      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:

        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:

          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

  2. Margriet Says:

    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:

      Pwoaaaaah! Grietje 🙂 Lang leve de kettingregel. Hier alles puik! Jij leuke verjaardag gehad vorige week? En had je m’n sms nog gekregen?

  3. Supplements Site Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: