# Carmichael Numbers

1. Apr 30, 2006

### Oxymoron

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

$$6601 = 7 \times 23 \times 41$$

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

$$p_i - 1 = n \quad \mbox{and } n | (6601 - 1)$$

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 $a^{q-1} - 1$. And from this we can say that

$$a^{q-1} \equiv 1(\mod p_i)$$

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

$$a^{6600} \equiv 1(\mod 7)$$
$$a^{6600} \equiv 1(\mod 23)$$
$$a^{6600} \equiv 1(\mod 41)$$

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

$$a^{6600} \equiv 1(\mod 6601) \quad \forall a\in\mathbb{Z}$$

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

2. Apr 30, 2006

### Oxymoron

duh! By the definition of a Carmichael number it is enough surely!