I was reading up on Carmichael numbers and I came across a brief proof that numbers of the form,(adsbygoogle = window.adsbygoogle || []).push({});

[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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# I do not understand this proof

**Physics Forums | Science Articles, Homework Help, Discussion**