- #1
Oxymoron
- 870
- 0
Ive been trying to prove that the number 6601 is a Carmichael number. I've 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
[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?
[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?