I do not understand this proof

[Oxymoron]

I was reading up on Carmichael numbers and I came across a brief proof that numbers of the form,

n = (6m+1)(12m+1)(18m+1)

where m \in \mathbb{Z} for which 6m+1, 12m+1, and 18m+1 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] 36m is a multiple of n-1 - which I proved easily via long division.

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

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

a^{n-1} \equiv 1(\mod 6m+1)

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

a^{n-1} \equiv 1(\mod 12m+1)

a^{n-1} \equiv 1(\mod 18m+1)

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

a^{n-1} \equiv 1(\mod n)

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

Have I got all 4 points correct?

 

[AKG]

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 a^6m = 1 (mod 6m+1). Likewise, we get a^12m = 1 (mod 12m+1), a^18m = 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).

 

[Oxymoron]

Thanks AKG. I made quite a few typos! But your explanation of [3] is great.

 

[shmoe]

[4] doesn't have much to do with the Chinese remainder theorem. You have 3 distinct primes dividing a^{n-1}-1, therefore their product divides it as well.