There are infinitely many Carmichael numbers (Q1334322): Difference between revisions

Carmichael numbers are those composite integers \(n\) for which \(a^ n\equiv a\bmod n\) for every integer \(a\). By a result of \textit{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 \textit{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 \textit{C. Pomerance} [Nieuw Arch. Wiskd., IV. Ser. 11, 199--209 (1993; Zbl 0806.11005)].