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

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)].


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
Full Text: DOI Link