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.