Carmichael Numbers: Understanding Their Significance and Properties

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