Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: [Phys-l] Carmichael numbers agai



The definition of a Carmichael number is that it is a composite number that
satisfies Fermat's "Little" Theorem.

That theorem states that if p is a prime number, then p divides (a^p - a) for
every integer a relatively prime to p, meaning divides exactly, with no remainder.

For example, it is easily seen by inspection that 2 divides a^2-a = a(a-1) for
all a; 3 divides a^3-a = (a+1)a(a-1) for all a, etc. On the other hand, 4 does
not divide 3^4-3 = 81-3 = 78 even though it divides 5^4-5 = 625 - 5 = 620.

But the converse of Fermat's Little Theorem is not true (as Fermat recognized):
it is not true that if n divides a^n - a for every a relatively prime to n,
that n is a prime. The exceptions, the composite numbers that DO satisfy
Fermat's Little Theorem, are called Carmichael or absolutely pseudoprime numbers.

It is known that Carmichael numbers are all odd; that they are all the product
of distinct (odd) primes, meaning none is divisible by a square such as 3^2 = 9
or 5^2 = 25; and that they all have at least 3 prime factors (many have more
than 5). Overall, the Carmichael numbers are rare. The two smallest are 561 =
3 x 11 x 17 and 1105 = 5 x 13 x 17. I don't believe it is known if the number
of Carmichael numbers is finite or infinite.

Exercise your mind! Prove that if a is not divisible by 3, 11, or 17, then 561
always divides (a^561 - a). :-)

Laurent Hodges