There are infinitely many Carmichael numbers. (English) Zbl 0816.11005

Alford, W. R.; Granville, Andrew; Pomerance, Carl

Ann. Math. (2) 139, No. 3, 703-722 (1994).

Carmichael numbers are those composite integers \(n\) for which \(a^ n\equiv a\bmod n\) for every integer \(a\). By a result of A. Korselt [L’intermédiaire des mathématiciens 6, 142–143 (1899)] \(n\) is a Carmichael number iff \(n\) is squarefree and \(p-1\) divides \(n-1\) for all primes \(p\) dividing \(n\). In this paper the authors show the existence of infinitely many Carmichael numbers.
They extend an idea of P. Erdős to construct integers \(L\) such that \(p-1\) divides \(L\) for a large number of primes \(p\). If there is a product of these primes \(\equiv 1\bmod L\), say \[ C= p_1\cdots p_k\equiv 1\bmod L \tag {*} \] then \(C\) is a Carmichael number which is shown by the criterion of A. Korselt mentioned above. In order to find integers with many divisors of the form \(p-1\), \(p\) prime, the authors generalize a theorem of K. Prachar [Monatsh. Math. 59, 91–97 (1955; Zbl 0064.04108)]. The question of the existence of products of the form \((*)\) leads to investigations in combinatorial group theory.
Reviewer’s remark: For a survey on Carmichael numbers, see the article of C. Pomerance [Nieuw Arch. Wiskd., IV. Ser. 11, 199–209 (1993; Zbl 0806.11005)].

Reviewer: Thomas Maxsein (Frankfurt / Main)

MSC:

11A25	Arithmetic functions; related numbers; inversion formulas
11N56	Rate of growth of arithmetic functions
11A07	Congruences; primitive roots; residue systems
11N69	Distribution of integers in special residue classes

Keywords:

divisors of the form \(p-1\); Carmichael numbers; existence of infinitely many Carmichael numbers; combinatorial group theory

Citations:

Zbl 0064.04108; Zbl 0806.11005