×

zbMATH — the first resource for mathematics

On the number of prime divisors of higher-order Carmichael numbers. (English) Zbl 1096.11003
The authors give lower bounds for the number of prime divisors of higher order Carmichael numbers as defined by E. W. Howe [“Higher-order Carmichael numbers”, Math. Comput. 69, 1711–1719 (2000; Zbl 0966.11006)]. A composite number \(n\) is a Carmichael number of order \(m\) if and only if \(n\) is squarefree and for every prime divisor \(p\) of \(n\) and for every integer \(r\) with \(1\leq r\leq m\), there is an integer \(i_r\geq 0\) such that \(n\equiv p^{i_r}\pmod{p^r-1}\). It is a rigid Carmichael number of order \(m\) if all \(i_r=0\) in this characterization. The authors prove that every Carmichael number of order \(m\) has at least \(m+2\) different prime divisors. Furthermore, they prove that if \(n\) is a Carmichael number of order \(m\geq 2\) and the largest prime divisor of \(n\) is larger than some given constant depending on \(m\), then \(n\) has at least \(s/2\) different prime divisors, where \(s=\sum_{k\leq m}\varphi(k)\) and \(\varphi\) denotes the Euler totient function. Finally, a rigid Carmichael number of order \(m\geq 2\) has at least \(s+1\) different prime divisors.
MSC:
11A51 Factorization; primality
11A25 Arithmetic functions; related numbers; inversion formulas
PDF BibTeX XML Cite