Ive been trying to prove that the number 6601 is a Carmichael number. Ive gone some way to prove it but I don't like it. The first thing I did was look up the prime factors of 6601. And they are(adsbygoogle = window.adsbygoogle || []).push({});

[tex]6601 = 7 \times 23 \times 41[/tex]

And then I noticed that for each prime factor [itex]p_i = \{7,23,41\}[/itex] we have

[tex]p_i - 1 = n \quad \mbox{and } n | (6601 - 1)[/tex]

So that 7 - 1 = 6 and 6 divides 6600, 22 divides 6600, and 40 divides 6600.

Now, Fermat's Little Theorem says that if a is an integer and q is coprime to a, then q divides [itex]a^{q-1} - 1[/itex]. And from this we can say that

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

So since 7-1 divides 6601-1 we can say that

[tex]a^{6600} \equiv 1(\mod 7)[/tex]

[tex]a^{6600} \equiv 1(\mod 23)[/tex]

[tex]a^{6600} \equiv 1(\mod 41)[/tex]

because 7, 23, and 41 all divide q-1. and a and q are coprime. Multiplying these together we get

[tex]a^{6600} \equiv 1(\mod 6601) \quad \forall a\in\mathbb{Z}[/tex]

But is this enough to prove that 6601 is a Carmichael Number?

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

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!

# Homework Help: Carmichael Numbers

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