1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: I do not understand this proof

  1. Apr 30, 2006 #1
    I was reading up on Carmichael numbers and I came across a brief proof that numbers of the form,

    [tex]n = (6m+1)(12m+1)(18m+1)[/tex]

    where [itex]m \in \mathbb{Z}[/itex] for which [itex]6m+1[/itex], [itex]12m+1[/itex], and [itex]18m+1[/itex] are all prime, are all Carmichael numbers.

    A quick search on this proof directed me to many of the various math reference sites and showed a number of properties which leads to the conclusion that n is a Carmichael number. These include

    [1] [itex]36m[/itex] is a multiple of [itex]n-1[/itex] - which I proved easily via long division.

    [2] The lowest common multiple of [itex]6m[/itex], [itex]12m[/itex], [itex]18m[/itex] is [itex]36m[/itex] - which surprisingly corresponds to [1].

    [3] Therefore since [itex]36m[/itex] divides [itex]n[/itex] and is the least common multiple of 6m, 12m, and 18m then for any integer a coprime to n,

    [tex]a^{n-1} \equiv 1(\mod 6m+1)[/tex]

    which is just a simple reverse application of Fermat's Little Theorem. The same can be said of 12m and 18m:

    [tex]a^{n-1} \equiv 1(\mod 12m+1)[/tex]

    [tex]a^{n-1} \equiv 1(\mod 18m+1)[/tex]

    [4] Therefore by a Corollary of F.L.T. we have

    [tex]a^{n-1} \equiv 1(\mod n)[/tex]

    So for any integer a coprime n. Which is exactly the definition of a Carmichael number.

    Have I got all 4 points correct?
  2. jcsd
  3. Apr 30, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    For [1], 36m is not a multiple of n-1. 36m DIVIDES n-1, and this follows immediately from looking at the equation n = (6m+1)(12m+1)(18m+1), i.e. no long division is required.

    For [3], 36m DOES NOT DIVIDE n, it divides n-1. Also, although the three congruences you have for [3] are correct when a is coprime to n, it has nothing to do with the reasoning you gave. If a is coprime to n, then clearly none of 6m+1, 12m+1, and 18m+1 can be a factor of a (otherwise it would be a common factor to a and n, but we're saying a and n are coprime). Since 6m+1 is not a factor of a, and since 6m+1 is a prime, FLT says that a6m = 1 (mod 6m+1). Likewise, we get a12m = 1 (mod 12m+1), a18m = 1 (mod 18m+1). Since 6m, 12m, and 18m all divide 36m, and 36m divides n-1, (and since any power of 1 is congruent to 1 (mod anything)), we get the congruences you end up with.

    For [4], I wouldn't say it follows from a corollary of FLT, I would say that it follows from the Chinese Remainder Theorem (plus the fact that 6m+1, 12m+1, and 18m+1 are all prime, hence coprime to one another).
  4. Apr 30, 2006 #3
    Thanks AKG. I made quite a few typos! :redface: But your explaination of [3] is great.
  5. Apr 30, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper

    [4] doesn't have much to do with the Chinese remainder theorem. You have 3 distinct primes dividing [tex]a^{n-1}-1[/tex], therefore their product divides it as well.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook