\input amstex \documentstyle{amsppt} \loadeusm \topmatter \title Frobenius Pseudoprimes \endtitle \date July 16, 1998 \enddate \email grantham\@super.org \endemail \author Jon Grantham \endauthor \subjclass{11Y11} \endsubjclass \address Institute for Defense Analyses, Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715 \endaddress \define\mepseudotwo{11} \define\mepseudothree{12} \abstract The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word ``pseudoprime'' in them. Examples include pseudoprimes, Euler pseudoprimes, strong pseudoprimes, Lucas pseudoprimes, strong Lucas pseudoprimes, extra strong Lucas pseudoprimes and Perrin pseudoprimes. Though these tests represent a wealth of ideas, they exist as a hodge-podge of definitions rather than as examples of a more general theory. It is the goal of this paper to present a way of viewing many of these tests as special cases of a general principle, as well as to re-formulate them in the context of finite fields. One aim of the reformulation is to enable the creations of stronger tests; another is to aid in proving results about large classes of pseudoprimes. \endabstract %\TagsOnLeft %\Monograph %\NoRunningHeads %\phantom{}\vskip.7in \NoBlackBoxes \def\as{2} \def\adams{1} \def\agp{3} \def\agptwo{4} \def\arno{5} \def\atkin{6} \def\bw{7} \def\gord{8} \def\gordpom{9} \def\mediss{10} \def\gurak{13} \def\guy{14} \def\jac{15} \def\ksw{16} \def\len{17} \def\mojones{18} \def\mon{19} \def\dopo{20} \def\pom{21} \def\psw{22} \def\rabin{23} \def\robin{24} \def\rot{25} \def\rots{26} \def\sze{27} \def\gcmd{\operatorname{gcmd}} \def\disc{\operatorname{disc}} \endtopmatter \document \head{\S 1 Introduction} \endhead Fermat's Little Theorem tells us that $a^{p-1}\equiv 1\bmod p$ for $p$ an odd prime; thus we have an easy way to prove that many numbers are composite. For example, since $2^{90}\equiv 64$ mod $91$, we prove that $91$ is composite. The technique of repeated squaring can be used to perform the required exponentiation very rapidly. This test is not foolproof. In particular, $2^{340}\equiv 1\bmod 341$. Composites which fool the test with $a=2$ are called pseudoprimes, and in general, composites $n$ with $a^{n-1}\equiv 1\bmod n$ are pseudoprimes to the base $a$. The existence of such numbers provides incentive to create other tests which are similarly fast, but which may have fewer, or at least different, ``pseudoprimes.'' Two of these tests are more elaborate versions of the test described above and create the notions of Euler pseudoprime and strong pseudoprime. Most other tests, however, involve recurrence sequences. One reason that pseudoprimes based on recurrence sequences have attracted interest is that the pseudoprimes for these sequence are often different from ordinary pseudoprimes. In fact, nobody has claimed the \$620 offered for a Lucas pseudoprime with parameters $(1,-1)$ (see \S 2 for a definition of this term), congruent to $2$ or $3\bmod 5$, that is also a pseudoprime to the base $2$ \cite{\psw, \guy}. Furthermore, some tests based on higher order recurrence sequences seem to have few pseudoprimes. Adams and Shanks \cite{\as} introduced such a test based on a third order recurrence sequence known as Perrin's sequence. A problem with tests based on recurrence sequences is that analysis of the tests can be difficult. For example, the concepts of Lucas and Lehmer pseudoprimes have been analyzed separately in the literature. In \S 2, we show that they are equivalent definitions. Instead of recurrence sequences, the language used in this paper is that of finite fields. In particular, when $n$ is a prime, $f(x)\in\Bbb{Z}[x]$, and $n$ does not divide $\disc(f)$, the residue ring $\Bbb{Z}[x]/(n,f(x))$ is a product of finite fields of characteristic $n$. When $n$ is composite, this ring is not equal to such a product. For a given composite $n$, this fact is often easy to discover, thus providing a quick proof of the compositeness of $n$. Using properties of finite fields, we establish the definition of Frobenius probable prime, which is a generalization, and sometimes a strengthening, of many existing definitions. We introduce the concept of Frobenius pseudoprimes, not to inflict a new and different notion of pseudoprimality on the mathematical world, but to show that many existing pseudoprimality tests can be generalized and described in terms of finite fields. In fact, we show that some specific instances of the Frobenius pseudoprime test are equivalent to other pseudoprimality tests, and stronger than many of them. In \cite{\mepseudotwo}, we use the structure given by the introduction of finite fields to show that the probability of error in declaring a number ``prime'' using a certain Frobenius test is less than $\frac 1{7710}$. In 1980, Monier \cite{\mon} and Rabin \cite{\rabin} proved that the Strong Probable Prime Test has probability of error at most $\frac 14$. Although the test introduced in \cite{\mepseudotwo} has asymptotic running time three times that of the Strong Probable Prime Test, the proven bound on the error is much smaller than the $\frac 1 {64}$ achieved through three Strong Probable Prime Tests. Perhaps the primary benefit of this approach is that instead of having to prove ten different theorems about ten different types of pseudoprimes, one can prove one theorem about Frobenius pseudoprimes and apply it to each type of pseudoprime. In \cite{\mepseudothree}, the techniques of \cite{\agp} are used to prove that for any monic, squarefree polynomial, there are infinitely many Frobenius pseudoprimes. In particular, this theorem answers a 1982 conjecture of Adams and Shanks \cite{\as} that there are infinitely many Perrin pseudoprimes. It also proves the infinitude of the types of pseudoprimes defined by Gurak \cite{\gurak} and Szekeres \cite{\sze}. We should note that the idea of primality testing in finite fields is not entirely new. Lenstra's Galois Theory Test \cite{\len} is a method of proving primality using finite fields. In \cite{\mediss}, I describe the relation between the two ideas. The combination of finite fields and pseudoprimes also exists implicitly in some other works, such as \cite{\sze}. The goal here, however, is different. I am trying to provide a clear theoretical framework in which various existing probable prime tests can be generalized and analyzed. \head{\S 2 A Wealth of Pseudoprimes} \endhead For the purposes of this paper, the following test for primality will be considered foolproof. If an integer is denoted by the letter $p$, then $p$ is prime. If $q$ is a prime power, we let $\Bbb{F}_q$ denote a finite field with $q$ elements. We begin by reviewing many of the existing notions of pseudoprimality. Each of these definitions of ``pseudoprime'' characterizes composite numbers with a certain property. In each of these cases, it can be proven that all prime numbers (with a finite, known set of exceptions) have this property. This paper does not pretend to be an exhaustive treatment of all notions of pseudoprimality. For example, nothing is said about elliptic pseudoprimes \cite{\gord}. Fermat's Little Theorem tells us that if $p$ is prime, then $a^{p-1}\equiv 1 \bmod p$, if $p\nmid a$. The original notion of a pseudoprime (sometimes called a Fermat pseudoprime) involves counterexamples to the converse of this theorem. \proclaim{Definition} A {\bf pseudoprime} to the base $a$ is a composite number $n$ such $a^{n-1}\equiv 1\bmod n$. \endproclaim \proclaim{Definition} A number $n$ which is a pseudoprime to all bases $a$ with $(a,n)=1$ is a {\bf Carmichael number}. \endproclaim We also know that if $p$ is an odd prime, then $\topsmash{a^{(p-1)/2}\equiv\left(a\over p\right)} \bmod p$, where $\topsmash{\left(a\over p\right)}$ is the Jacobi symbol. The converse of this theorem leads to the definition of Euler pseudoprime, due to Raphael Robinson \cite{\robin}. \proclaim{Definition} An {\bf Euler pseudoprime} to the base $a$ is an odd composite number $n$ with $(a,n)=1$ such that $a^{(n-1)/2}\equiv\left(a\over n\right) \bmod n$. \endproclaim An Euler pseudoprime to the base $a$ is also a pseudoprime to the base $a$. If $n\equiv 1 \bmod 4$, we can also look at $a^{(n-1)/{2^k}}$ for $k>1$, and doing so gives us the definition of strong pseudoprime \cite{\psw}, due independently to R. Dubois and John Selfridge. \proclaim{Definition} A {\bf strong pseudoprime} to the base $a$ is an odd composite $n=2^rs+1$ with $s$ odd such that either $a^s\equiv 1 \bmod n$, or $a^{2^ts}\equiv -1$ for some integer $t$, with $r>t\ge 0$. \endproclaim A strong pseudoprime to the base $a$ is also an Euler pseudoprime to the base $a$ \cite{\mon, \psw}. It is possible to define notions of pseudoprimality based on congruence properties of recurrence sequences. The simplest of these are based on the Lucas sequences $U_n(P,Q)$, where $P$ and $Q$ are integers, $U_0=0$, $U_1=1$ and $U_n=PU_{n-1}-QU_{n-2}$. (When $P=1$ and $Q=-1$, this is the Fibonacci sequence.) We recall the fact that we can express $U_n$ in terms of roots of the polynomial $f(x)=x^2-Px+Q$. If $\alpha$ and $\beta$ are roots of $f(x)$ in a commutative ring (with identity), with $\alpha-\beta$ invertible, then $U_n=(\alpha^n-\beta^n)/(\alpha-\beta)$. By induction on $n$, this equality holds even if there are more than two distinct roots of $f(x)$. \proclaim{Theorem 2.1} Let $U_n=U_n(P,Q)$ and $\Delta=P^2-4Q$. If $p\nmid 2Q\Delta$, then $\botsmash{U_{p-\left(\Delta\over p\right)}}\equiv 0 \bmod p$. \endproclaim \demo{Proof} Since $p\nmid\Delta$, $x^2-Px+Q$ has distinct roots, $\alpha$ and $\beta$, in $\bar\Bbb{F}_p$. If $\left(\Delta\over p\right)=1$, then $f(x)$ factors mod $p$, and $\alpha$ and $\beta$ are in $\Bbb{F}_p$. Thus $\alpha^{p-1}\equiv \beta^{p-1}\equiv 1\bmod p$. So $U_{p-1}\equiv (1-1)/(\alpha-\beta)=0\bmod p$. If $\left(\Delta\over p\right)=-1$, then $f(x)$ does not factor, and the roots of $f(x)$ lie in $\Bbb{F}_{p^2}$. The Frobenius automorphism permutes the roots of $f(x)$, so $\alpha^p\equiv\beta$ and $\beta^p\equiv\alpha$. Thus $U_{p+1}\equiv(\alpha\beta-\beta\alpha)/(\alpha-\beta)=0\bmod p$. \enddemo \proclaim{Definition} Let $U_n=U_n(P,Q)$ and $\Delta=P^2-4Q$. A {\bf Lucas pseudoprime} with parameters $(P,Q)$ is a composite $n$ with $(n,2Q\Delta)=1$ such that $U_{n-\left(\Delta\over n\right)}\equiv 0 \bmod n$. \endproclaim Baillie and Wagstaff \cite{\bw} gave a version of this test that is analogous to the strong pseudoprime test. We first define the sequence $V_n(P,Q)$ to be the sequence with $V_0=2$, $V_1=b$, and $V_n=PV_{n-1}-QV_{n-2}$. Note that $V_n=\alpha^n+\beta^n$, where $\alpha$ and $\beta$ are distinct roots of $x^2-Px+Q$. \proclaim{Theorem 2.2} Let $U_n=U_n(P,Q)$ and $\Delta=P^2-4Q$. Let $p$ be a prime not dividing $2Q\Delta$. Write $p=2^rs+\left(\Delta\over p\right)$, where $s$ is odd. Then either $U_s\equiv 0$ or $V_{2^ts}\equiv 0 \bmod p$ for some $t$, $0\le t < r$. \endproclaim \demo{Proof} As above, since $p\nmid\Delta$, $x^2-Px+Q$ has distinct roots in $\bar\Bbb{F}_p$. If $\left(\Delta\over p\right)=1$, the roots $\alpha$ and $\beta$ are elements of $\Bbb{F}_p$. If $\botsmash{\left(\Delta\over p\right)}=-1$, they are elements of $\Bbb{F}_{p^2}$. Their product is $\alpha\beta=Q\neq 0$, so $\beta\neq 0$. We have that $U_{2^rs}=(\alpha^{2^rs}-\beta^{2^rs})/(\alpha-\beta)\equiv 0 \bmod p$. Thus $(\alpha/\beta)^{2^rs}\equiv 1$ mod $p$. Taking square roots, we have that either $(\alpha/\beta)^{2^ts}\equiv -1$ for some $t$ with $0\le t1$ is said to pass the {\bf Frobenius probable prime test} with respect to $f(x)$ if $(n,f(0)\Delta)=1$, and it is declared to be a probable prime by the following algorithm. (Such an integer will be called a {\bf Frobenius probable prime} with respect to $f(x)$.) All computations are done in $(\Bbb{Z}/n\Bbb{Z})[x]$. {\bf Factorization Step} Let $f_0(x)=f(x) \bmod n$. For $1\le i\le d$, let $F_i(x)=\gcmd(x^{n^i}-x,f_{i-1}(x))$ and $f_i(x)=f_{i-1}(x)/F_i(x)$. If any of the $\gcmd$s fail to exist, declare $n$ to be composite and stop. If $f_d(x)\not=1$, declare $n$ to be composite and stop. {\bf Frobenius Step} For $2\le i\le d$, compute $F_i(x^n) \bmod F_i(x)$. If it is nonzero for some $i$, declare $n$ to be composite and stop. {\bf Jacobi Step} Let $S=\sum\Sb{2|i}\endSb\deg(F_i(x))/i$. If $(-1)^S\not=\left(\Delta\over n\right)$, declare $n$ to be composite and stop. \vskip.05in If $n$ is not declared to be composite by one of these three steps, declare $n$ to be a Frobenius probable prime and stop. \endproclaim The Factorization Step produces a ``distinct degree'' factorization when $n$ is prime. It may be of some interest to apply algorithms that factor the polynomials completely, thus developing definitions for Berlekamp and Cantor-Zassenhaus probable primes. The Cantor-Zassenhaus algorithm shares ideas with the ``strong'' Frobenius probable prime test of Section 5. Berlekamp's algorithm has two forms; one deterministic and one probabilistic. The deterministic version has running time proportional to $n$, so it is too slow to be used in primality testing. The probabilistic version is fast, but since it is significantly more complicated than most existing probable prime tests, we omit consideration of it here. \proclaim{Corollary 3.6} Every odd prime $p$ is a Frobenius probable prime with respect to any monic polynomial $f(x)$ such that $p$ does not divide $f(0)\Delta$. \endproclaim \demo{Proof} Immediate from Theorem 3.1. \enddemo \proclaim{Definition} Let $f(x)\in\Bbb{Z}[x]$. A {\bf Frobenius pseudoprime} with respect to a monic polynomial $f(x)$ is a composite which is a Frobenius probable prime with respect to $f(x)$. \endproclaim \head{\S 4 The Relation of Frobenius Pseudoprimes to Other Pseudoprimes} \endhead \proclaim{Theorem 4.1} An odd integer $n$ is a pseudoprime to the base $a$ if and only if it is a Frobenius pseudoprime with respect to the polynomial $f(x)=x-a$. \endproclaim \demo{Proof} First, assume $n$ is an pseudoprime to the base $a$. Thus, $a^{n-1}\equiv 1 \bmod n$. Since $\Delta=1$, $(n,f(0)\Delta)=(n,a)=1$. Because $(x-a)|(x^n-a^n)$ and $a^n-a=0$ in $(\Bbb{Z}/n\Bbb{Z})[x]$, we have $(x-a)|((x^n-a^n)+(a^n-a)+(a-x))$ or $(x-a)|(x^n-x)$. Therefore, $F_1(x)=x-a$, and $f_1(x)=1$, so $n$ passes the Factorization Step. Since $d=1$, The Frobenius Step is vacuous. Note that $S=0$ and $\left(\Delta\over n\right)=\left(1\over n\right)=1$, so $n$ passes the Jacobi Step. Therefore $n$ is a Frobenius pseudoprime. Now, assume $n$ is a Frobenius pseudoprime with respect to $x-a$. In order to have $f_1(x)=1$, we must have $F_1(x)=x-a$. So by the Factorization Step, $(x-a)|(x^n-x)$. Since $(x-a)|(x^n-a^n)$, $(x-a)$ divides $a^n-a$. Since the latter is a constant and $x-a$ is monic, $a^n-a$ must be $0$ in $(\Bbb{Z}/n\Bbb{Z})[x]$. So $a^n\equiv a \bmod n$. Since $(n,f(0)\Delta)=(n,a)=1$, we have $a^{n-1}\equiv 1 \bmod n$. Thus $n$ is a pseudoprime to the base~$a$. \enddemo In fact, a more general result can be proven: a Frobenius pseudoprime with respect to $f(x)$ is a pseudoprime to the base $f(0)$. The idea for the proof can be found in \cite{\gurak}, Corollary 1. We first need to prove a lemma about polynomials mod $p^k$. \proclaim{Lemma 4.2} Let $g(y)$ be a polynomial in $\Bbb{Z}[y]$, irreducible mod $p$. Let $f(x)$ be a polynomial in $\Bbb{Z}[x]$ with $p\nmid\disc(f)$. If $f(x)$ has $d$ roots in $(\Bbb{Z}[y]/(p,g(y)))[x]$, then it has $d$ roots in $(\Bbb{Z}[y]/(p^k,g(y)))[x]$ for $k$ a positive integer. \endproclaim \demo{Proof} By Hensel's Lemma, a root mod $p$ lifts to exactly one root mod $p^k$, since the discriminant of $f$ is non-zero mod $p$. Hensel's Lemma applies to any finite field of characteristic $p$. \enddemo \proclaim{Theorem 4.3} Let $f(x)$ be a monic, squarefree polynomial in $\Bbb{Z}[x]$. If an odd integer $n$ is a Frobenius pseudoprime with respect to $f(x)$, then it is a pseudoprime to the base $f(0)$. \endproclaim \demo{Proof} It suffices to prove $f(0)^n\equiv f(0) \bmod p^k$ for every prime power $p^k|n$. Let $d$ be the degree of $f(x)$. There exists an extension field of $\Bbb{F}_p$, $\Bbb{F}_{p}[y]/(g(y))$, in which $f(x)$ splits completely. The $d$ roots must be distinct, since $n$ is coprime to the discriminant of $f(x)$. Thus there are $d$ distinct roots of $f(x)$ in $\Bbb{Z}[y]/(p^k,g(y))$, by Lemma 4.2. Call the roots $y_1,y_2,\dots,y_d$. Consider the map $y_i\mapsto y_i^n$. By the Frobenius Step, this map sends each root to another root. By the Factorization Step, $\left(y_i^n\right)^{n^{d-1}}=y_i$, so the map is invertible. Therefore, it permutes the roots. Thus $\prod_{i=1}^d y_i=\prod_{i=1}^d y_i^n$. But $\prod_{i=1}^d y_i\equiv (-1)^df(0) \bmod p$, so $(-1)^df(0)\equiv ((-1)^df(0))^n \bmod p^k$. Simplifying, we see that $f(0)^n\equiv f(0) \bmod p^k$ for each $p^k|n$. Thus $n$ is a pseudoprime to the base $f(0)$. \enddemo Theorem 4.3 can be used, in conjunction with results about the distribution of pseudoprimes base $a$, to give an upper bound on the number of Frobenius pseudoprimes with respect to a given polynomial $f(x)$. \proclaim{Corollary 4.4} Let $f(x)\in\Bbb{Z}[x]$ be a monic polynomial with nonzero discriminant. If $|f(0)|\not=1$, then the number of Frobenius pseudoprimes with respect to $f(x)$ up to $y$ is less than $y^{1-\log\log\log y/2\log\log y}$, for $y$ sufficiently large, where ``sufficiently large'' depends only on $|f(0)|$. \endproclaim \demo{Proof} Immediate from Theorem 4.3 and \cite{\pom}. \enddemo When $|f(0)|=1$, it is possible that all integers are Frobenius pseudoprimes with respect to $f(x)$, such as if $f(x)=x-1$. In fact, we conjecture that for every monic, squarefree polynomial $f(x)$, not the product of cyclotomic polynomials, the bound of Corollary 4.4 holds. For quadratic polynomials, the conjecture follows from \cite{\gordpom}. \proclaim{Theorem 4.5} If $a,\ b$ are integers, $f(x)=(x-a)(x-b)$, and $n$ is a Frobenius pseudoprime with respect to $f(x)$, then $n$ is a pseudoprime to both bases $a$ and $b$. \endproclaim \demo{Proof} Since $f(x)$ factors, its discriminant must be a square, so $\left(\Delta\over n\right)=1$. Therefore $F_2(x)=1$ and $F_1(x)=f(x)$ by the Jacobi Step. Since $f(x)|(x^n-x)$, we have $(x-a)|(x^n-x)$. Therefore, as in the proof of Theorem 4.1, we conclude $n$ is a pseudoprime to the base $a$ and, similarly, base $b$. \enddemo \proclaim{Theorem 4.6} If $f(x),g(x)\in\Bbb{Z}[x]$ with $(n,\disc(fg))=1$ and $n$ is a Frobenius pseudoprime with respect to $f(x)$ and $g(x)$, then it is a Frobenius pseudoprime with respect to $f(x)g(x)$. \endproclaim \demo{Proof} Let $h(x)=f(x)g(x)$. Let $f_i(x),g_i(x),h_i(x)$ and $F_i(x),G_i(x),H_i(x)$ be the polynomials produced in the Factorization Steps for $f(x),g(x),h(x)$, respectively. If a polynomial is not defined in that step (e.g., $f_{d+1}(x)$, if $f(x)$ has degree $d$), define it to be $1$. We will show by induction on $i$ that $h_i(x)=f_i(x)g_i(x)$ and $H_i(x)=F_i(x)G_i(x)$. We have that $h_0(x)=h(x)=f(x)g(x)=f_0(x)g_0(x)$. Assume that $h_{k-1}(x)=f_{k-1}(x)g_{k-1}(x)$. By definition, we have $H_k(x)=\gcmd(x^{n^k}-x,h_{k-1}(x))$, should this $\gcmd$ exist. Since $F_k(x)|f_{k-1}(x)$, $G_k(x)|g_{k-1}(x)$, $F_k(x)G_k(x)|h_{k-1}(x)$. Because $\gcd(\disc(fg),n)=1$, we have that $\gcd(F_k(x),G_k(x))=1$ in $\Bbb{F}_p[x]$ for each $p|n$. By Proposition 3.4, $\gcmd(F_k(x),G_k(x))=1$ in $(\Bbb{Z}/n\Bbb{Z})[x]$. Therefore $F_k(x)A_1(x)+G_k(x)A_2(x)\equiv 1\bmod n$ for some $A_1(x)$ and $A_2(x)$ in $\Bbb{Z}[x]$. Also, $x^{n^k}-x\equiv B_1(x)F_k(x)\equiv B_2(x)G_k(x)$, for some $B_1(x)$ and $B_2(x)$ in $\Bbb{Z}[x]$, by the definitions of $F_k(x)$ and $G_k(x)$. Thus $F_k(x)B_1(x)\equiv G_k(x)B_2(x)\bmod n$. Multiplying by $A_1(x)$ gives $F_k(x)A_1(x)B_1(x)\equiv G_k(x)A_1(x)B_2(x)$. If we substitute for $F_k(x)A_1(x)$, we get $(1-G_k(x)A_2(x))B_1(x)\equiv G_k(x)A_1(x)B_2(x)$, or $B_1(x)\equiv G_k(x)[A_2(x)B_1(x)+A_1(x)B_2(x)]$. Hence $G_k(x)|B_1(x)$, and $F_k(x)G_k(x)|x^{n^k}-x$. Thus $F_k(x)G_k(x)|H_k(x)$. We have, by the definitions of $F_k(x)$ and $G_k(x)$, that $F_k(x)\equiv r_1(x)(x^{n^k}-x)+s_1(x)f_{k-1}(x)$ and $G_k(x)\equiv r_2(x)(x^{n^k}-x)+s_2(x)g_{k-1}(x)$, for some polynomials $r_1(x)$, $r_2(x)$, $s_1(x)$, and $s_2(x)$. Multiplying these two congruences together, $F_k(x)G_k(x)\equiv r_3(x)(x^{n^k}-x)+s_1(x)s_2(x)h_{k-1}(x)$, where $r_3(x)=r_1(x)r_2(x)(x^{n^k}-x)+r_1(x)s_2(x)g_{k-1}(x)+r_2(x)s_1(x)f_{k-1}(x)$. Therefore, $H_k(x)=F_k(x)G_k(x)$. Now $h_k(x)=h_{k-1}(x)/H_{k-1}(x)$, so by the inductive hypothesis, $$h_k(x)=f_{k-1}(x)g_{k-1}(x)/(F_{k-1}(x)G_{k-1}(x))= f_k(x)g_k(x).$$ Each of the $\gcmd$s in the Factorization Step exists, and $h_{\deg(fg)}(x)=1$. Thus $n$ passes the Factorization Step. Since $H_i(x)=F_i(x)G_i(x)$, and $n$ passes the Frobenius Step for $f(x)$ and $g(x)$, $H_i(x)|H_i(x^n)$. Thus $n$ passes the Frobenius Step for $h(x)$. Let $S_f$ and $S_g$ be the values of $S$ computed in the Jacobi Step for $f(x)$ and $g(x)$, respectively. Then $S=S_f+S_g$. So it suffices to show that $\left(\disc(fg)\over n\right)= \left(\disc(f)\over n\right)\left(\disc(g)\over n\right)$. To show this equality, it suffices to show that $\disc(fg)=\disc(f)\disc(g)\ell^2$, where $\ell\in\Bbb{Z}$. Let $\alpha_1,\dots,\alpha_j$ be the roots of $f(x)$ and $\alpha_{j+1},\dots,\alpha_d$ be the roots of $g(x)$, all in $\bar\Bbb{Q}$. Then $\disc(fg)=\prod_{ij$. Thus $\sigma$ must only rearrange terms in the product, and $\sigma(\ell)=\ell$. Thus $\left(\disc(fg)\over n\right)= \left(\disc(f)\over n\right)\left(\disc(g)\over n\right)$, $n$ passes the Jacobi Step, and $n$ is a Frobenius pseudoprime with respect to $f(x)g(x)$. \enddemo The converse to Theorem 4.6 is true for the product of two linear polynomials, as Theorems 4.1 and 4.5 show. It is not, however, true in general. If $f(x)=(x-1341)(x-513)(x-545)$, then $1537$ is a Frobenius pseudoprime with respect to $f(x)$, but it is not a pseudoprime to any of the bases $1341$, $513$, or $545$. This example appears in \cite{\as} and indicates the possible usefulness of the quadratic forms test contained therein. The examples produced in that paper, however, all involve polynomials with relatively large discriminant compared to the pseudoprimes. \proclaim{Corollary 4.7} If $n$ is a Carmichael number, $f(x)\in\Bbb{Z}[x]$ is monic, $f(x)$ factors into linear factors mod $n$ and $(n,f(0)\Delta)=1$, then $n$ is a Frobenius pseudoprime with respect to $f(x)$. \endproclaim \demo{Proof} Apply Theorem 4.1 and Theorem 4.6. \enddemo \proclaim{Lemma 4.8} Let $m,n$ be positive integers, and let $f(x),g(x),r(x)\in\Bbb{Z}[x]$. If $f(r(x))\equiv 0 \bmod (n,f(x))$ and $x^m \equiv g(x) \bmod (n,f(x))$, then $r(x)^m \equiv g(r(x)) \bmod (n,f(x))$. \endproclaim \demo{Proof} $x^m\equiv g(x)+f(x)h(x) \bmod n$, for some $h(x)\in\Bbb{Z}[x]$. Since $x$ is an indeterminate, $r(x)^m\equiv g(r(x))+f(r(x))h(r(x)) \bmod n$. Because $f(r(x))\equiv 0 \bmod (n,f(x))$, $r(x)^m\equiv g(r(x)) \bmod (n,f(x))$. \enddemo \proclaim{Theorem 4.9} If $f(x)=x^2-Px+Q\in\Bbb{Z}[x]$, and $n$ is a Frobenius pseudoprime with respect to $f(x)$, then $n$ is a Lucas pseudoprime with parameters $(P,Q)$. \endproclaim \demo{Proof} Note that $S=0$ or $1$. If $\left(\Delta\over n\right)=1$, then we must have $S=0$, so $x^n\equiv x \bmod (n,f(x))$. Since $Q$ is invertible mod $n$, $x$ is invertible mod $(n,f(x))$. Thus $x^{n-1}\equiv 1$. By Lemma 4.8, $(P-x)^{n-1}\equiv 1$, since $f(P-x)\equiv 0 \bmod (n,f(x))$. The two roots of $f(x)$ in $\Bbb{Z}[x]/(f(x))$ are $x$ and $P-x$, and $(x-(P-x))^2\equiv P^2-4Q \bmod f(x)$. Since $n$ is coprime to the discriminant $P^2-4Q$, the difference of the two roots is invertible. Thus $U_{n-1}\equiv \frac{x^{n-1}-(P-x)^{n-1}}{x-(P-x)}\equiv \frac{1-1}{2x-P}=0 \bmod (n,f(x))$. If $\left(\Delta\over n\right)=-1$, then we must have $S=1$, so $x^n\not\equiv x \bmod (n,f(x))$. We cannot have $x^n\equiv x \bmod (p^k,f(x))$ for $p^k|n$, since then $x^n-x\equiv 0 \bmod (p^k,f(x))$, and the gcmd in the Factorization Step would not exist. Because $p\nmid\Delta$, there are only 2 roots to $f(x) \bmod (p^k,f(x))$, by Lemma 4.2. Since they are known to be $x$ and $P-x$, we must have $x^n\equiv P-x \bmod (p^k,f(x))$ for each prime power $p^k|n$, by the Frobenius Step. Since $f(x)$ is monic, the congruence must hold mod $(n,f(x))$ by the Chinese Remainder Theorem. By Lemma 4.8, $(P-x)^n\equiv x \bmod (n,f(x))$, so $U_{n+1}\equiv\frac{x^{n+1}- (P-x)^{n+1}}{2x-P}\equiv \frac{x(P-x)-(P-x)x}{2x-P}=0$. \enddemo Note that the Frobenius test is in fact stronger than the Lucas test. For example, $323$ is the first Lucas pseudoprime with respect to the Fibonacci sequence. If we compute $x^{323}-x \bmod (323,x^2-x-1)$, we get $-1$. So $F_1(x)=1$. If we compute $x^{323^2}-x \bmod (323,x^2-x-1)$, we get $0$. So $F_2(x)=x^2-x-1$ and $f_2(x)=1$. So $323$ passes the Factorization Step. Note that it also passes the Jacobi Step, since $\left({5}\over 323\right)=-1$. But it fails the Frobenius Step, because $x^{323}\equiv x-1 \bmod (323,x^2-x-1)$, and $F_2(x-1)=-2x+2$. The first Frobenius pseudoprime with respect to the Fibonacci polynomial $x^2-x-1$ is $5777$. \proclaim{Theorem 4.10} If $f(x)=x^3-rx^2+sx-1$, then any Frobenius pseudoprime $n$ with respect to $f(x)$ is also a Perrin pseudoprime. In particular, if $F_1(x)=f(x)$, then $n$ has an S-signature, if $F_3(x)=f(x)$, then $n$ has an I-signature, and if $\deg(F_1)=1$ and $\deg(F_2)=2$, $n$ has a Q-signature. \endproclaim \demo{Proof} The idea behind this proof is that relationships between $n$th powers of the roots determine the signature, and the necessary relationships are guaranteed to hold because $n$ passes the Frobenius Probable Prime Test. To this end, we use Lemma 2 of \cite{\as}. Let $K$ be the splitting field of $f(x)$. Let $\alpha_1$, $\alpha_2$ and $\alpha_3$ be the three roots of $f(x)$ in $K$. Lemma 2 says that $n$ has a Q-~signature if for each prime power $p^k|n$, and for each prime ideal $\frak{p}$ of $K$ with $\frak{p}|p$, $\alpha_1^n\equiv \alpha_1$, $\alpha_2^n\equiv\alpha_3$, and $\alpha_3^n\equiv\alpha_2 \bmod \frak{p}^k$ (or some other permutation of the roots of order 2.) If $\deg(F_1)=1$ and $\deg(F_2)=2$, then we must have $f(x)\equiv F_1(x)F_2(x) \bmod p^k$. So $f(\alpha)=0\equiv F_1(\alpha)F_2(\alpha)$. Because the discriminant of $f(x)$ is not divisible by $p$, we know that $F_1(x)$ has exactly one root mod $p^k$, by Lemma 4.2. Therefore, one of the roots (say $\alpha_1$) is a root of $F_1(x)$ and the other two are roots of $F_2(x)$. For $\alpha_1$, we have $x^n\equiv x \bmod (p^k,F_1(x))$. But we must have $F_1(x)\equiv x-\alpha_1 \bmod p^k$, so $\alpha_1^n\equiv\alpha_1 \bmod p^k$, and hence for every prime ideal power dividing $p^k$. We have $x^n\not\equiv x \bmod (p^k,F_2(x))$, but $F_2(x^n)\equiv 0$. Since there are only two roots of $F_2(x)$, we must have $\alpha_2^n\equiv \alpha_3 \bmod p^k$, and similarly $\alpha_3^n\equiv\alpha_2$. The proofs of the S and I cases are similar. \enddemo \proclaim{Theorem 4.11} Let $f(x)\in\Bbb{Z}[x]$ be a monic, squarefree polynomial. Let $\beta_1,\dots,\beta_d$ be its roots, and let $V_k=\beta_1^k+\dots+\beta_d^k$. If $n$ is a Frobenius pseudoprime with respect to $f(x)$, then $n$ is a pseudoprime with respect to $V$, in the sense of \cite{\gurak}, Section 4. \endproclaim \demo{Proof} The theorem follows directly from Theorem 2 of \cite{\gurak}. \enddemo \proclaim{Theorem 4.12} Let $f(x)$ be a monic, squarefree polynomial. If $n$ is a Frobenius pseudoprime with respect to $f(x)$, then $n$ is a pseudoprime in the sense of Szekeres. \endproclaim \demo{Proof} It suffices to show that the map $x\mapsto\topsmash{x^n}$ permutes the roots of $f(x)$. This fact follows from the Frobenius Step. \enddemo Having presented the definition of Frobenius pseudoprime as a generalization of other definitions of pseudoprime, we would like to use the above theorems to produce a theorem that holds for all of these types of pseudoprimes. \proclaim{Conjecture 4.13} For any monic, squarefree polynomial $f(x)\in\Bbb{Z}[x]$, there are infinitely many Frobenius pseudoprimes with respect to $f(x)$. In fact, for any $\epsilon>0$, there exists a $T$ (depending on $f(x)$ and $\epsilon$) such that if $t>T$, there are at least $t^{1-\epsilon}$ Frobenius pseudoprimes less than $t$. \endproclaim It is straightforward to prove the first assertion for many polynomials (those which split into linear and quadratic factors over $\Bbb{Z}$). The proof uses Corollary 4.7 and an extension of results in \cite{\agp} and \cite{\agptwo}. It is possible to prove this statement for all polynomials, but the proof requires results about L-functions over number fields. The proof is given in \cite{\mepseudothree}. The second assertion seems considerably more difficult to prove; for a discussion of impediments, see \cite{\agp}. \head{\S 5 Strong Frobenius Pseudoprimes} \endhead We can strengthen the test developed in the previous section by using the identity $x^{n^i-1}-1=(x^s-1)\botsmash{\prod_{j=1}^r (x^{2^{j-1}s}+~1)}$ (where $n^i-1=2^rs$) to further factor $F_i(x)$. \proclaim{Theorem 5.1} Let $f(x)$, $d$, $\Delta$, $p$, and $F_i(x)$ be as in Theorem 3.1. Let $p^i-1=2^rs$ with $s$ odd. Let $F_{i,0}(x)=\gcd(F_i(x),x^s-1)$. For $1\le j\le r$, let $F_{i,j}(x)=\gcd(F_i(x),x^{2^{j-1}s}+1)$. Then $\botsmash{\prod_{j=0}^r F_{i,j}(x)=F_i(x)}$ and for each $j$, the degree of $F_{i,j}(x)$ is divisible by $i$. \endproclaim \demo{Proof} We have the identity $\topsmash{x^{p^i-1}-1=(x^s-1)\prod_{j=1}^r(x^{2^{j-1}s}+1)}$. The result follows since the factors in the product are pairwise coprime, and since $f(0)\ne 0$. \enddemo \proclaim{Definition} Let $f(x)\in\Bbb{Z}[x]$ be a monic polynomial of degree $d$ with discriminant $\Delta$. An odd integer $n$ with $(n,f(0)\Delta)=1$ is said to pass the {\bf strong Frobenius probable prime test} with respect to $f(x)$ if it is a Frobenius probable prime and is declared to be a probable prime by the following additional step. (Such an integer will be called a {\bf strong Frobenius probable prime} with respect to $f(x)$.) {\bf Square Root Step} For each $1\le i\le d$, let $n^i-1=2^rs$ with $r$ odd. Let ${F}_{i,0}(x)=\gcmd(F_i(x),x^s-1)$. Let ${F}_{i,j}(x)=\gcmd({F}_i(x), x^{2^{j-1}s}+1)$. Then if ${F}_i(x)\neq\prod_{j=0}^r F_{i,j}(x)$, if for some $j$, the degree of $F_{i,j}(x)$ is not a multiple of $i$, or if one of the $\gcmd$s fails to exist, declare $n$ to be composite and terminate. If $n$ is not declared to be composite by the Frobenius probable prime test or the Square Root Step, declare $n$ to be a strong Frobenius probable prime. \endproclaim \proclaim{Corollary 5.2} Every odd prime $p$ is a strong Frobenius probable prime with respect to any monic polynomial $f(x)$ such that $p$ does not divide $f(0)\Delta$. \endproclaim \proclaim{Definition} A {\bf strong Frobenius pseudoprime} with respect to a monic polynomial $f(x)\in\Bbb{Z}[x]$ is a composite strong Frobenius probable prime with respect to $f(x)$. \endproclaim Clearly every strong Frobenius pseudoprime with respect to $f(x)$ is a Frobenius pseudoprime with respect to $f(x)$. \proclaim{Theorem 5.3} A number $n$ with $(n,2a)=1$ is a strong Frobenius pseudoprime with respect to $x-a$ if and only if $n$ is a strong pseudoprime to the base $a$. \endproclaim \demo{Proof} From Theorem 3.1 it suffices to show that a pseudoprime to the base $a$ is strong if and only if it passes the Square Root Step with respect to $x-a$. In order to pass the Square Root Step, we need to have $x-a|x^{2^{r-j}s}+1$ for some $1\le j\le r$ or $x-a|x^s-1$. The first statement is equivalent to $a^{2^{r-j}s}\equiv -1 \bmod n$ and the second is equivalent to $a^s\equiv 1 \bmod n$. These are exactly the conditions for strong pseudoprimality. So $n$ passes the Square Root Step if and only if it is a strong pseudoprime to the base $a$. \enddemo \proclaim{Corollary 5.4} Every strong Frobenius pseudoprime with respect to $x-a$ is an Euler pseudoprime to the base $a$. \endproclaim The situation with strong Lucas pseudoprimes is a bit more complicated, as the polynomial needs to be changed. \proclaim{Theorem 5.5} Let $f(x)=x^2-Px+Q$. Let $n$ be a integer with $(n,2\Delta Q)=1$. Let $Q'$ be an integer with $Q'\equiv Q^{-1} \bmod n$. If $n$ is a strong Frobenius pseudoprime with respect to $X^2+(2+b^2c')X+1$, then $n$ is a strong Lucas pseudoprime with parameters $(P,Q)$. \endproclaim \demo{Proof} Let $U_k=U_k(P,Q)$ and $V_k=V_k(P,Q)$. Note that $U_k\equiv 0 \bmod n$ if and only if $x^k-(P-x)^k\equiv 0 \bmod (n,x^2-Px+Q)$ if and only if $\left(\frac{P-x}x\right)^k \equiv 1$. Similarly, $V_k \equiv 0$ if and only if $\left(\frac{P-x}x\right)^k\equiv -1$. Let $X=-Q'Px+Q'P^2-1$. Then $X\equiv (P-x)/x \bmod (n,x^2-Px+Q)$ and $X^2+(2-P^2Q')X+1=(PQ')^2(x^2-Px+Q)$. So, by a change of variables, we see that $U_k\equiv 0 \bmod n$ if and only if $X^k\equiv 1 \bmod \looseness=1 (n,X^2+(2-P^2Q')X+1)$. The same statement holds for $V_k$, with $1$ replaced by $-1$. So $U_k\equiv 0 \bmod n$ if and only if $X^2+(2-P^2Q')X+1$ divides $X^k-1$. Using this statement, the fact that $n$ is a strong Lucas pseudoprime with parameters $(P,Q)$ follows immediately from the Square Root Step. \enddemo If we insist on keeping the same polynomial, a weaker result can be proven. \proclaim{Theorem 5.6} Every strong Frobenius pseudoprime $n$ with respect to $f(x)=x^2-Px+Q$ such that $\left(P^2-4Q\over n\right)=-1$ is a strong Lucas pseudoprime with parameters $(P,Q)$. \endproclaim \demo{Proof} Let $U_k=U_k(P,Q)$ and $V_k=V_k(P,Q)$. Write $n+1=2^RS$ and $n^2-1=2^rs$ with $s$ and $S$ odd. Note that $2^rs=(n-1)2^RS$, so $R 0$. This means that either $f(x)|x^{2^{r-R}s}-1$ or $f(x)|x^{2^{r-j}s}+1$ for some $j$ such that $R\ge j>0$. In the first case, we observe $2^{r-R}s=(n-1)S=nS-S$. So $x^{nS-S}\equiv 1 \bmod (n,f(x))$, or $x^{nS}\equiv x^S$. But we know that $x^n\equiv (P-x)$, so $(P-x)^S\equiv x^S$. Thus $U_S \equiv (x^S-(P-x)^S)/(x-(P-x))\equiv 0 \bmod (n,f(x))$ and thus mod $n$. In the second case, we use the formula $2^{r-j}s=(n-1)2^{R-j}S=n2^{R-j}S-2^{R-j}S$. But $x^{2^{r-j}s}\equiv -1 \bmod (n,f(x))$, so $x^{2^{R-j}S}\equiv -x^{n2^{R-j}S}$. This gives us that $x^{2^{R-j}S}\equiv -(P-x)^{2^{R-j}S}$. Since $V_m\equiv x^m+(P-x)^m$, $V_{2^{R-j}S}\equiv 0 \bmod n$. We conclude that $n$ is a strong Lucas pseudoprime. \enddemo Theorem 5.6 would not be true without the restriction that $\left(b^2+4c\over n\right)=-1$. For example, $294409$ is a strong Frobenius pseudoprime with respect to $x^2-1185x+56437$, but it is not a strong Lucas pseudoprime with parameters $(1185,56437)$. \proclaim{Theorem 5.7} If $n$ is a strong Frobenius pseudoprime with respect to $x^2-bx+1$, then $n$ is an extra strong Lucas pseudoprime to the base $b$. \endproclaim \demo{Proof} Let $U_k=U_k(b,1)$ and $V_k=V_k(b,1)$. Assume that $\left(b^2+4\over n\right)=-1$. Let $R,r,S,s$ be as in the proof of Theorem 5.6. Observe that $x^{n+1}\equiv x(b-x) \equiv 1$. If $f(x)|x^{2^{r-j}s}+1$ for some $j$ such that $r\ge j>0$, then we have that $V_{2^{R-j}s}\equiv 0$, as in Theorem 5.6. If $V_{2^{r-1}s}\equiv 0$, we have that $V_{\frac{n+1}2}\equiv 0$, so $x^{\frac{n+1}2}+(b-x)^{\frac{n+1}2}\equiv 0$. Since $(b-x)\equiv x^{-1}$, we deduce $x^{n+1}\equiv -1$, a contradiction. This establishes that $j>1$, as the definition of extra strong Lucas pseudoprime requires. If $f(x)|x^s-1$, this means that $x^s\equiv 1 \bmod (n,f(x))$. $s=S(n-1)/2^{r-R}$. So $\gcd(\frac sS,n+1)=1$. Therefore $x^S\equiv 1$, and $V_S \equiv x^S+(b-x)^S \equiv 1+1=2$, and $U_S \equiv 0$ as above. Similarly, if $f(x)|x^s+1$, we have $V_S\equiv -2$ and $U_S\equiv 0$. The only remaining case is $f(x)|x^{2^{r-j}s}+1$ for some $j$ such that $r >j \ge R+1$. $r>R+1$ only if $n\equiv 1 \bmod 4$. Then $R=1$, and $j\le r-1$. So $2^{r-j}s=(n+1)\frac{n-1} {2^j}$, and $x^{2^{r-j}s}\equiv x^{(n+1)\frac{n-1}{2^j}}\equiv 1$. This contradicts the assumption that $f(x)|x^{2^{r-j}s}+1$. The proof for the case where the Jacobi symbol is $1$ is similar. \enddemo \head{\S 6 Carmichael-Frobenius Numbers} \endhead A Carmichael number is to be a number which is a (Fermat) pseudoprime to every base. With that in mind, we make the following definition. \proclaim{Definition} Let $K$ be a number field and $n$ an odd composite with $(n,\disc(K))=1$. If, for each polynomial $f(x)\in\Bbb{Z}[x]$ with all its roots in $K$ and $(n,f(0)\disc(f))=1$, $n$ is a Frobenius pseudoprime with respect to $f(x)$, then $n$ is a {\bf Carmichael-Frobenius number} with respect to $K$. \endproclaim Note that $n$ is a Carmichael number if and only if it is a Carmichael-Frobenius number with respect to $\Bbb{Q}$. Also, if $n$ is a Carmichael-Frobenius number with respect to $K$, then it is also a Carmichael-Frobenius number with respect to any subfield of $K$. In particular, a Carmichael-Frobenius number with respect to $K$ is also a Carmichael number. \proclaim{Proposition 6.1} Let $n$ be a Carmichael number, and let $K$ be a number field with $(n,\disc(K))=1$. If every prime $p|n$ splits completely in $K$, then $n$ is a Carmichael-Frobenius number with respect to $K$. \endproclaim \demo{Proof} Let $f(x)\in\Bbb{Z}[x]$ be a polynomial with all of its roots in $K$ such that $\gcd(n,f(0)\disc(f))=1$. For each $p|n$, $f(x)$ must split into linear factors mod $p$, since $p$ splits completely in $K$. Since $n$ is a Carmichael number, it is squarefree, so $f(x)$ splits into linear factors mod $n$. The Proposition follows from Corollary 4.7. \enddemo These Carmichael-Frobenius numbers have $F_1(x)=f(x)$ in the Factorization Step for each $f(x)$ with all of its roots in $K$. In \cite{\mepseudothree}, we will show that there are infinitely many of them for each number field $K$. Other types of Carmichael-Frobenius numbers are harder to come by. The methods of \cite{\dopo} can be used to give heuristics suggesting that there are infinitely many Carmichael-Frobenius numbers with respect to $K$ with $F_2(x)=f(x)$ for each irreducible $f(x)$ with all of its roots in $K$. We also have the following Proposition, which is similar to Proposition 6 of \cite{\gurak}. \proclaim{Proposition 6.2} Let $f(x)\in\Bbb{Z}[x]$ be a monic, irreducible polynomial of degree $k$ with splitting field $K$. Let $n$ be a Carmichael-Frobenius number with respect to $K$. If $F_k(x)= f(x)$ in the Factorization Step of the Frobenius Probable Prime Test with respect to $f(x)$, then $n$ has at least $k+2$ prime factors. \endproclaim \demo{Proof} Let $p$ be a prime factor of $n$, and let $f_p(x)$ be an irreducible factor of $f(x)$ of maximal degree in $\Bbb{F}_p[x]$. Let $A_p=\Bbb{F}_p[x]/(f_p(x))$. We have that $A_p =\Bbb{F}_{p^r}$ for some $r\ge 1$. We will show that $r=k$. Since $x^n$ is a root of $f(x)$ in $\Bbb{Z}[x]/(n,f(x))$, it is a root in $A_p$, and we must have $x^n=x^{p^t}$ in $A_p$, for some $t>0$. We thus have $x^{n^r}\equiv x^{p^{tr}}\equiv x$ in $A_p$. Thus $f_p(x)|\gcd(f(x),x^{n^r}-x)$ in $\Bbb{F}_p[x]$. Since all $\gcmd$s were computable, $f_p(x)|F_{r'}(x)$, for some $r'\le r$. But since $F_k(x)=f(x)$, we must have $r'=k$, and thus $r=k$. Let $\alpha$ be a root of $f(x)$ in $K$. Then for some $g_p(x)\in\Bbb{Z}[x]$, $g_p(\alpha)$ has order $p^k-1$ in $A_p^*$. By the Chinese Remainder Theorem, there is a monic polynomial $g(x)\in\Bbb{Z}[x]$ such that $g(x)\equiv g_p(x) \bmod p$ for each $p|n$. Let $h(x)$ be the minimal polynomial of $g(\alpha)$ over $\Bbb{Q}$. Then $h(x)$ has all of its roots in $K$. Since $h(x)$, considered mod $p$, is the minimal polynomial for $g_p(\alpha)$, we have $p\nmid h(0)\disc(h)$ for each $p|n$, and thus $\gcd(n,h(0)\disc(h))=1$. Thus $h(x^n)=0$ in $A_p$. But the roots of $h(x)$ in $A_p$ are $x^p, x^{p^2},\dots, x^{p^{k-1}}, x^{p^k}$. Then $n\equiv p^t\bmod (p^k-1)$, for some $1\le t \le r$. This congruence gives $p^k-1|n-p^t$, for some $1\le t\le k$. Therefore, $p^k-1|\frac np-p^{t-1}$. Since $n$ is a Carmichael number, it is not a prime power, and $n>p^t$, which implies $\frac np-p^{t-1}>0$. So $p^k-1\le \frac np-p^{t-1}\le \frac n p-1$; thus $p^k\le \frac np$. Since $n\neq p^{k+1}$, $p^k<\frac np$. Thus we have for all $p|n$, $p^k<\frac np$, or $p^{k+1}