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

    AKG

    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

    shmoe

    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