Return to Colloquia & Seminar listing
Higher-order Carmichael numbers
ColloquiumSpeaker: | Everett Howe, Center for Communications Research, La Jolla |
Location: | 693 Kerr |
Start time: | Mon, Nov 4 2002, 4:10PM |
Fermat's little theorem states that if n is a prime number, then a^n - a is a multiple of n for every integer a. The converse of Fermat's little theorem is false: there exist composite numbers n such that a^n - a is a multiple of n for every integer a, the smallest example being n = 561 = 3*11*17. Such numbers are called Carmichael numbers, after the mathematician Robert D. Carmichael (1879--1967). Erdos gave a heuristic argument that indicated that there should be infinitely many Carmichael numbers, and in a technically difficult 1994 paper Alford, Granville, and Pomerance used an argument based on Erdos's heuristic to prove that for large values of x, there are more than x^(2/7) Carmichael numbers less than x. In this talk I will introduce the "higher-order" Carmichael numbers, which behave even more like primes than do the original Carmichael numbers. They arise from considering a natural ring-theoretic interpretation of the definition of the usual Carmichael numbers. A variant of Erdos's argument indicates that there should be infinitely many Carmichael numbers of order m for every m > 0, but we do not even know whether there exist *any* Carmichael numbers of order 3. I will show how Erdos's argument and some non-trivial computation can produce examples of Carmichael numbers of order 2.