# On Carmichael Numbers

1. Oct 9, 2009

### thomas430

Hi everyone :-)

at http://mathworld.wolfram.com/CarmichaelNumber.html it says that a Carmichael number is one which satisfies Fermat's little theorem:

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

for every choice of a which is co-prime to n, with 1 < a < n.

Why is the domain 1 < a < n specified?

A maths book that I'm reading says "Can it happen that n is a pseudoprime to all possible bases a? The answer is yes and such numbers are called Carmichael numbers."

Does this mean that the set (1,n) exhausts all possible bases a?

Thanks :-)

Thomas.

2. Oct 9, 2009

### ramsey2879

Yes, because $$(a +bn)^{n-1} = a^{n-1} \mod n$$.
Therefore you do not have to check the coprime numbers greater than n. Can you see why that is so?

Last edited: Oct 9, 2009
3. Oct 9, 2009

### thomas430

I see how that works.. and I expanded for n=3 to get a taste.

Thanks, ramsey!

4. Oct 11, 2009

### robert Ihnot

Thomas 430: Does this mean that the set (1,n) exhausts all possible bases a?

We are only considering coprime numbers, so that n==0 Mod n is not considered.

By coprime there are only $$\Phi (n)$$ (Euler totient function) such possibilities. For example for n=15 there are only $$\Phi(3)*\Phi 5 = 8$$ such numbers that form the multiplicative group.

5. Oct 15, 2009

### thomas430

Thanks Robert, that makes good sense.

6. Oct 15, 2009