On Carmichael Numbers

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

[ramsey2879]

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

[thomas430]

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

Thanks, ramsey!

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

[thomas430]

Thanks Robert, that makes good sense.

[robert Ihnot]

Thanks Robert, that makes good sense.

Good! Glad to hear.