Pseudoprimes and Fermat numbers (Q6542781)

Given a positive integer \(b>1\), a pseudoprime to base \(b\) is a composite positive integer \(n\) which satisfies Fermat's little theorem, namely: \(b^{n-1}\equiv1\pmod n\). It is well-known that the converse of Fermat's little theorem does not hold, and the previous congruence can be considered a test for primality of a positive integer \(n\). Roughly speaking, given an integer \(n\), if the congruence of Fermat's little theorem holds for several different bases \(b\) then \(n\) is likely to be prime. However, the integers \(n\) which are pseudoprime to every base \(b\) coprime to \(n\) which are called Carmichael numbers are known to be infinitely many, even if they are sparse compared to primes [\textit{W. R. Alford} et al., Ann. Math. (2) 139, No. 3, 703--722 (1994; Zbl 0816.11005)].\N\NA more reliable primality test proposed by \textit{M. O. Rabin} [J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)] and \textit{L. Monier} [Theor. Comput. Sci. 12, 97--108 (1980; Zbl 0443.10002)] is based on the following notion: a composite integer \(n\) such that either \(b^d\equiv 1\pmod{n}\) or \(b^{d\cdot 2^i}\equiv-1\pmod n\) for some \(i\in\{0,\ldots,k-1\}\) holds, then \(n\) is called a strong pseudoprime to base \(b\). Clearly, every prime number \(n\) satisfies either one of the previous two congruences. The set of strong pseudoprimes to some base \(b\) is a proper subset of the set of pseudoprimes to the same base \(b\).\N\NIn Section 2, given an integer \(n\), let \(\mathbb F_n\) (\(\mathbb R_n\), resp.) be the set of all pseudoprime (strong pseudoprime, resp.) bases for \(n\) in \(\{1,\ldots,n-1\}\). Clearly, \(\mathbb F_n\) is a group under multiplication modulo \(n\). The author proves that \(\mathbb R_n\) is a subgroup of \(\mathbb F_n\) if and only if either \(n\) is divisible by a prime \(p\equiv 3\pmod 4\) or \(n\) is a prime power. In particular, the set of all odd composite integer \(n\) for which \(\mathbb R_n\) is not a subgroup of \(\mathbb F_n\) has asymptotic density \(0\).\N\NIn Section 3, the author characterizes a subset of the bases for which a Fermat number \(F_k=2^{2^k}+1\) is a strong pseudoprime. Since no prime \(p\) congruent to \(3\) modulo \(4\) is divides a Fermat number, these numbers falls into the aforementioned class of asymptotic density \(0\).\N\NIn Section 4, the author shows that there is a polynomial-time algorithm to factor a composite integer \(n\) which is a Lucas pseudoprime and not a strong Lucas pseudoprime (such notions have been introduced by \textit{R. Baillie} and \textit{S. S. Wagstaff jun.} [Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)].