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 be a Carmichael number, such that and are primes. Then we have the following :

Contradiction :).

EDIT: I am terribly sorry, but I made some huge, stupid mistakes here.

Mistake 1: A Carmichael number is a composite number such that, for every COPRIME , we have . If I assume , I can’t say that , because and are *not* coprime.

Mistake 2: I assumed . Why may I assume that? The answer is that I just can’t! could very well be , 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.

### Like this:

Like Loading...

*Related*

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.

October 14, 2010 at 16:42 |

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

October 14, 2010 at 17:32 |

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!!

October 20, 2010 at 12:29 |

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?

October 20, 2010 at 16:04 |

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

October 15, 2010 at 17:39 |

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.

October 15, 2010 at 18:32 |

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

March 17, 2015 at 07:30 |

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.