On Lucas and Frobenius Pseudoprimes}
Full text
#A107 INTEGERS 25 (2025) ON LUCAS AND FROBENIUS PSEUDOPRIMES Lawrence Somer Department of Mathematics, Catholic University of America, Washington, D.C. [email protected] Michal Kˇr´ıˇzek Institute of Mathematics, Czech Academy of Sciences, Prague, Czech Republic [email protected] Received: 12/30/24, Revised: 5/22/25, Accepted: 11/3/25, Published: 11/25/25 Abstract Consider the Lucas sequences U(P, Q) and V(P, Q) which satisfy the linear recurrence relation Wn+2 =PWn+1−QWnwith initial terms U0= 0, U1= 1, and V0= 2, V1=P, respectively, where Pand Qare integers. We consider pseudoprimes with parameters Pand Qrelated to U(P, Q) and V(P, Q). We extend results obtained by Somer and Kˇr´ıˇzek (2022) regarding pseudoprimes with parameters Pand Q, where Pis odd and greater than 0 to those in which the parameter Pcan also be less than 0 or even. We also obtain infinitely many new examples of pseudoprimes, called the Lucas pseudoprimes with parameters Pand Q. We further present results on Frobenius pseudoprimes, which are generalizations of Lucas pseudoprimes. – Dedicated to Professor Curtis Cooper on the occasion of his retirement. 1. Introduction Let Pand Qbe integer numbers. Let U(P, Q), called the Lucas sequence of the first kind (LSFK), and V(P, Q), called the Lucas sequence of the second kind (LSSK), be the sequences satisfying the linear recursion relation Wn+2 =PWn+1 −QWn(n≥0) (1.1) with discriminant D=P2−4Qand the initial terms W0and W1are U0= 0, U1= 1 and V0= 2, V1=P, respectively. In this paper, we will extend results obtained by Somer and Kˇr´ıˇzek [22] concerning pseudoprimes related to the Lucas sequences U(P, Q) and V(P, Q). These results are generalized from pseudoprimes with parameters Pand Qfor which Pis greater DOI: 10.5281/zenodo.17711594
INTEGERS: 25 (2025) 2 than 0 and odd to additional cases in which Pcan also be less than 0 or even. We will also obtain infinitely many new cases of one type of pseudoprime defined below in Definition 3.1, called the Lucas pseudoprimes with parameters Pand Q. We also discuss Frobenius pseudoprimes which are generalizations of Lucas pseudoprimes. 2. Necessary Definitions and Results To proceed, we will require the following definitions and results. If mis a positive integer, it is easily seen that U(P, Q) and V(P, Q) are purely periodic modulo mwhen gcd(m, Q) = 1 (see [5, pp. 344–345]). From here on, we assume that gcd(m, Q) = 1. Throughout this paper, pand pidenote primes and malways represents a positive integer. We denote the period of U(P, Q) modulo mby λ(m), that is, λ(m) is the least positive integer ssuch that Us+n≡un(mod m) for all n≥0. The rank of appearance of min U(P, Q), denoted by ρ(m), is the least positive integer rsuch that Ur≡0 (mod m). Since U0= 0 and U(P, Q) is purely periodic modulo m, we see that ρ(m) exists. It is clear that Ut≡0 (mod m) if and only if ρ(m)|t. The prime pis called a primitive prime divisor of Un(P, Q)ifρ(p)=n. Equivalently, pis a primitive prime divisor of Un(P, Q) if p|Un(P, Q), but p∤Ui(P, Q) for 1 ≤i≤n−1. Associated with U(P, Q) and V(P, Q) is the characteristic polynomial f(x) = x2−Px +Q with discriminant D=D(P, Q)=P2−4Qand characteristic roots α= (P+√D)/2 and β= (P−√D)/2.(2.1) We observe that D= (α−β)2.(2.2) It follows from (2.1), (2.2), the Binet formulas, and the binomial formula that Un(P, Q) = αn−βn √D= ⌊(n−1)/2⌋ X k=0 n 2k+ 11 2n−1Pn−(2k+1)Dk(2.3) and Vn(P, Q)=αn+βn= ⌊n/2⌋ X k=0 n 2k1 2n−1Pn−2kDk.(2.4)
INTEGERS: 25 (2025) 3 The Lucas sequences U(P, Q) and V(P, Q) with characteristic roots αand βare called degenerate if PQ = 0 or α/β is a root of unity. It follows from the Binet formulas (2.3) and (2.4) that Un(P, Q)orVn(P, Q) can be equal to 0 for some n > 0 only if U(P, Q) and V(P, Q) are degenerate. Since the characteristic polynomial of U(P, Q) and V(P, Q) is a quadratic polynomial with integer coefficients, one sees that α/β can be a primitive nth root of unity only if n∈ {1,2,3,4,6}. The following theorem determines all degenerate Lucas sequences U(P, Q) and V(P, Q). Theorem 2.1. Let Mdenote an arbitrary nonzero integer. Then the Lucas sequences U(P, Q)and V(P, Q)with characteristic roots αand βare degenerate only in the following cases: (i) Q= 0,Pis any integer. Then D=P2,Un=Pn−1, and Vn=Pnfor n≥1. (ii) α/β = 1. Then P= 2M,Q=M2, and D= 0. (iii) α/β =−1. Then P= 0,Q=M, and D=−4M. (iv) α/β is a primitive cube root of unity. Then P=M,Q=M2, and D= −3M2. (v) α/β is a primitive fourth root of unity. Then P= 2M,Q= 2M2, and D=−4M2. (vi) α/β is a primitive sixth root of unity. Then P= 3M,Q= 3M2, and D= −3M2. This is proved in [23, p. 613]. Remark 2.2. Consider the nondegenerate LSFK U(P, Q), where Q=±1. We note that by Theorem 2.1, D=P2−4Q>0. The following Proposition 2.3, Theorem 2.4, Lemmas 2.5–2.9, and Corollary 2.10 will be needed for the proof of our principal results. Proposition 2.3. Consider the nondegenerate Lucas sequences U(P, Q)and V(P, Q). Then the following hold: (i) U2n=UnVn; (ii) U2 n+1 −UnUn+2 =Qn; (iii) if m|n, then Um|Un; (iv) if m|nand n/m is odd, then Vm|Vn; (v) P|U2nfor all n≥0;
INTEGERS: 25 (2025) 4 (vi) P|Vnfor nodd; (vii) Un(−P, Q)=(−1)n+1Un(P, Q); (viii) Vn(−P, Q)=(−1)nVn(P, Q). Proof. Parts (i)–(iv) and (vii)–(viii) follow from the Binet formulas (2.3) and (2.4). Part (v) follows from part (iii) and part (vi) follows from part (iv) upon noting that U2=V1=P. Theorem 2.4. Consider the LSFK U(P, Q)and the LSSK V(P, Q)with discriminant D. Let rand sbe positive integers. (i) If gcd(r, Q)=1, then r|Usif and only if ρ(r)|s; (ii) if pis an odd prime and p∤Q, then p|Up−(D/p), where (D/p)is the Legendre symbol and (D/p)=0if p|D; (iii) if p|Dand p∤Q, then ρ(p) = p; (iv) if p∤2QD, then U(p−(D/p))/2if and only if (Q/p) = 1; (v) if p∤Q,ρ(pk)=ρ(p), and ρ(pk+1)=ρ(p), then ρ(pj) = pmax(j−k,0)ρ(p)for j≥1; (vi) if gcd(rs, Q) = 1 and r|s, then ρ(r)|ρ(s); (vii) if gcd(P, Q)=1and d= gcd(r, s), then gcd(Ur, Us)=|Ud|; (viii) if gcd(r, s) = gcd(rs, Q)=1, then ρ(rs) = lcm(ρ(r), ρ(s)); (ix) if gcd(P, Q)=1and p|Q, then p∤Unfor n≥1; (x) if gcd(P, Q)=1, then p≡(D/p) (mod ρ(p)). This follows from the results in [12, pp. 53–74], [4], and [9]. Lemma 2.5. Consider the LSFK U(P, Q), where Q= 0. Let W(P, Q)be a recurrence satisfying the recursion relation (1.1) with initial terms W0and W1. Suppose that Ut≡0 (mod m), where gcd(m, Q)=1. Then Wn+t≡Ut+1Wn(mod m) for all n≥0.
INTEGERS: 25 (2025) 5 Proof. It can be shown by induction and use of the linear recursion relation defining both U(P, Q) and W(P, Q) that Wn+s=−QWn−1Us+WnUs+1. Thus, Wn+t≡ −QWn−1Ut+WnUt+1 ≡ −QWn−1·0 + WnUt+1 ≡Ut+1Wn(mod m) for all n≥0. Lemma 2.6. Consider the Lucas sequence U(P, Q), where gcd(P, Q) = 1. Let pbe a prime such that pi∥U2=P, where pi∥U2means that pi|U2, but pi+1 ∤U2. Let nbe a positive integer. Then pi+1 |U2nif and only if p|n. In particular, gcd(U2n/P, P)=1if gcd(n, P ) = 1. Proof. This follows from Theorem X of [4]. Lemma 2.7. Let U(P, Q)be a Lucas sequence for which 2∤gcd(P, Q). (i) U(P, Q)is purely periodic modulo 2. (ii) Suppose Pis odd and Qis even. Then 2∤Unfor n≥1. (iii) Suppose Pis even and Qis odd. Then 2|Unif and only 2|n. Moreover, 2|D. (iv) Suppose Pand Qare both odd. Then 2|Unif and only 3|n. Proof. This follows by inspection of U(P, Q) modulo 2. Lemma 2.8. Let U(P, Q)be a Lucas sequence for which 3∤gcd(P, Q). (i) U(P, Q)is purely periodic modulo 3. (ii) If 3|Q, then 3∤Unfor n≥1. (iii) If 3|P, then ρ(3) = 2 and 3|Unif and only if 2|n. (iv) If 3∤Pand Q≡ −1 (mod 3), then ρ(3) = 4 and 3|Unif and only if 4|n. (v) If 3∤Pand Q≡1 (mod 3), then ρ(3) = 3 and 3|Unif and only if 3|n. Moreover, 3|D. Proof. This follows by inspection of U(P, Q) modulo 3. Lemma 2.9. Let U(P, Q)and V(P, Q)be nondegenerate Lucas sequences such that D > 0. Then |Un|is increasing for n≥2and |Vn|is increasing for n≥1. Further, if P > 0, then Un>0for n≥1and Vn>0for n≥0. Moreover, if it is not the case that |P|=−Q= 1, then |U3|≥3.
INTEGERS: 25 (2025) 6 This follows from Lemma 3 of [6] and Lemma 2.8 of [10]. The following corollary is immediate from Lemma 2.9. Corollary 2.10. Let U(P, Q)be a nondegenerate LSFK such that D > 0. Then ρ(Un)=nfor n≥3. 3. Pseudoprimes Related to the Lucas Sequences U(P, Q) and V(P, Q) It follows from Theorem 2.4 (ii) and (iv) and the Binet formulas (2.3) and (2.4) that if Nis an odd prime such that gcd(N, PQD) = 1, then the following four congruences are all satisfied for the Lucas sequences U(P, Q) and V(P, Q) with discriminant D, where (D/N) denotes the Jacobi symbol (also see [2, pp. 1391, 1392, 1396]): UN−(D/N)≡0 (mod N),(3.1) UN≡(D/N) (mod N),(3.2) VN≡P(mod N),(3.3) VN−(D/N)≡2Q1−(D/N))/2(mod N).(3.4) It also occurs rarely that at least one of the four congruences (3.1)–(3.4) holds if Nis a positive odd composite integer. We note that by [2, p. 1392], any two of the four congruences above imply the other two when Nis a positive odd integer. We have the following definitions which are given in [16]. Definition 3.1. The positive odd composite integer Nis called a Lucas pseudoprime with parameters Pand Qif gcd(N, QD) = 1 and congruence (3.1) holds. (We simply denote Nas a Lucas pseudoprime if the parameters Pand Qare understood.) Definition 3.2. The positive odd composite integer Nis called a Lucas pseudoprime of the second kind with parameters Pand Qif gcd(N, QD) = 1 and congruence (3.2) holds. Definition 3.3. The positive odd composite integer Nis called a Dickson pseudoprime with parameters Pand Qif gcd(N, QD) = 1 and congruence (3.3) holds. Definition 3.4. The positive odd composite integer Nis called a Dickson pseudoprime of the second kind with parameters Pand Qif gcd(N, QD) = 1 and congruence (3.4) holds. For particular pairs of parameters Pand Qit is known that there exist infinitely many odd composite integers Nthat satisfy each of the congruences (3.1)–(3.4) (see Theorem 1 of [14]). This gives rise to the following definition appearing in [16].
INTEGERS: 25 (2025) 7 Definition 3.5. The positive odd composite integer Nis called a Frobenius pseudoprime with parameters Pand Qif gcd(N, PQD) = 1 and congruences (3.1)–(3.4) all hold. In [22] we found families of Lucas pseudoprimes and Frobenius pseudoprimes with parameters Pand Qin which P > 0 and Pis odd. In this paper, we will generalize these results by removing the restriction on Pand allowing negative values of P as well as permitting Pto be even. In both this paper and [22], we give special attention to the situation in which Q=±1. In addition, the definitions of the five types of pseudoprimes given below will be needed for our further work. Definition 3.6. Let Nbe a positive odd composite integer and let abe a positive odd integer such that gcd(a, N) = 1. Then Nis called a pseudoprime to the base a if an−1≡1 (mod N). Definition 3.7. Let Nbe a positive odd composite integer and let abe a positive odd integer such that gcd(a, N) = 1. Then Nis called an Euler pseudoprime to the base aif a(N−1)/2≡1 (mod N) if (a/N) = 1 or a(N−1)/2≡ −1 (mod N) if (a/N)=−1. It is clear that Nis a pseudoprime to the base aif Nis an Euler pseudoprime to the base a. Remark 3.8. Let Nbe a positive odd integer and let Q=±1. Then by the properties of the Jacobi symbol, Q(N−1)/2= (Q/N), and Nis always an Euler pseudoprime to the base Q. Definition 3.9. Consider the LSFK U(P, Q) and the LSSK V(P, Q). The positive odd composite integer Nis called an Euler–Lucas pseudoprime with parameters P and Qif gcd(N, QD) = 1 and U(N−(D/N))/2≡0 (mod N) if (Q/N) = 1 or V(N−(D/N))/2≡0 (mod N) if (Q/N) = −1. Definition 3.10. Consider the LSFK U(P, Q) and the LSSK V(P, Q). Let Nbe a positive odd composite integer such that gcd(N, QD) = 1 and N−(D/N)=2sd, where dis odd. Then Nis called a strong Lucas pseudoprime with parameters P and Qif either
INTEGERS: 25 (2025) 8 (i) Ud≡0 (mod N), or (ii) V2rd≡0 (mod N) for some rwith 0 ≤r < s. Remark 3.11. It follows from Proposition 2.3 (i) and (iii) that Euler–Lucas pseudoprimes and strong Lucas pseudoprimes are Lucas pseudoprimes. Theorem 3.12. Consider the LSFK U(P, Q). Let Nbe a positive odd composite integer Nsuch that gcd(N, QD) = 1. If Nis a strong Lucas pseudoprime, then N is an Euler–Lucas pseudoprime. This is proved in Theorem 3 of [2]. Definition 3.13. The positive odd composite integer Nis called a super Lucas pseudoprime with parameters Pand Qif gcd(N, QD) = 1 and each divisor of N greater than 1 is a prime or a Lucas pseudoprime with parameters Pand Q.Super Frobenius pseudoprimes and super strong Lucas pseudoprimes with parameters P and Qare defined similarly. Theorems 3.14 and 3.16 given below provide necessary and sufficient criteria for an odd composite integer Nto be a strong Lucas pseudoprime or a super Lucas pseudoprime. Theorem 3.14. Consider the nondegenerate LSFK U(P, Q). Let N= s Y i=1 pki i be an odd composite integer such that gcd(N, PQD)=1. Suppose that Nis a Lucas pseudoprime. Then ρ(pki i)=pifor 1≤i≤s. If Nis also a strong Lucas pseudoprime, then ν2(ρ(pi))=ν2(ρ(pj)) for 1≤i<j≤s, where ν2(m)=iif pi|m, but pi+1 ∤m. Conversely, if Nis a Lucas pseudoprime such that ν2(ρ(pi))=ν2(ρ(pj)) for 1≤i<j≤s, then Nis in addition a strong Lucas pseudoprime. This is proved in Proposition 2.18 of [22]. Corollary 3.15. Consider the nondegenerate LSFK U(P, Q). Let Nbe a Lucas pseudoprime for which gcd(N, QD) = 1. Then, Nis in addition a strong Lucas pseudoprime if ρ(N)is odd. Proof. By Theorem 2.4 (vi), if p|N, then ρ(p)|ρ(N). The result now follows from Theorem 3.14.
INTEGERS: 25 (2025) 9 Theorem 3.16. Consider the nondegenerate LSFK U(P, Q). Let p1, p2, . . . , psbe distinct odd primes each relatively prime to QD such that ρ(pmi i) = ρ(pi), but ρ(pmi+1 i)=ρ(pi)for i∈ {1, . . . , s}. Let h= lcm(ρ(p1), ρ(p2), . . . , ρ(ps)). Let Nbe an odd composite integer such that N= s Y i=1 pki i, where 1≤ki≤mi. Then ρ(N)=hand Nis a super Lucas pseudoprime if and only if for each i= 1,...,s, pi≡(D/pi) (mod h). This is proved in Theorem 2.22 of [22]. Theorem 3.17. Consider the nondegenerate LSFK U(P, Q). Let N= s Y i=1 pki i be an odd composite integer such that gcd(N, PQD) = 1. Suppose that ρ(pki i)=ρ(pi) = ρ(pkj j)=ρ(pj) for 1 ≤i < j ≤s. Then Nis a super strong Lucas pseudoprime. Additionally, if Q=±1, then Nis also a super Frobenius pseudoprime. This follows from the proof of Proposition 2.23 in [22]. Theorem 3.18. Consider the nondegenerate LSFK U(P, Q). Suppose that Nis an Euler–Lucas pseudoprime with parameters Pand Qand that Nis also an Euler pseudoprime to the base Q, where gcd(N, PQD) = 1. Then Nis a Frobenius pseudoprime. This is proved in Theorem 1 of [15]. Theorem 3.19. Consider the nondegenerate LSFK U(P, Q), where Q=±1. Suppose that Nis a positive odd composite integer such that gcd(N, P D) = 1. If Nis a strong Lucas pseudoprime, then Nis a Frobenius pseudoprime. Proof. By Theorem 3.12, Nis also an Euler–Lucas pseudoprime with parameters Pand Q. By Remark 3.8, Nis moreover an Euler pseudoprime to the base Q. It now follows from Theorem 3.18 that Nis a Frobenius pseudoprime.
INTEGERS: 25 (2025) 16 pseudoprime if it is not the case that (p, P, Q) = (5,±1,2) or (5,±1,3) or (5,±2,3) or (5,±12,55) or (13,±1,2). Moreover, |U10(±1,2)|= 11,|U10(±1,3)|= 31,|U10(±2,3)/2|= 11, |U10(±12,55)/12|= 3739,|U26(±1,2)|= 181,(5.3) which are all primes. Proof. By Proposition 2.3 (v), P|U2p. We note that U1= 1, U2=P, and gcd(p, P) = 1. It then follows from Lemma 2.6, Proposition 2.3 (iii), and Theorem 2.4 (i) that the only prime divisors of N2=|U2p/P|are the primitive prime divisors of Upand U2p. We now show that if |U2p/P |is composite, then N2=|U2p/P|is a super Lucas pseudoprime. Since N2|U2p, it follows that ρ(N2)|2p. Suppose that q1is a primitive prime divisor of Up. By Theorem 2.4 (ii), (iii), and (x), q1≡(D/q1) (mod p), where (D/q1)=±1, since p∤D. As q1−(D/q1) is even and pis odd, it follows that q1≡(D/q1) (mod 2p). Further by Theorem 2.4 (ii), (iii), and (x), if q2 is a primitive prime divisor of U2p, then q2≡(D/q2) (mod 2p), where (D/q2)=±1, since 2p=ρ(q2) is not a divisor of D. We now see by Theorem 3.16 that N2is a super Lucas pseudoprime if |U2p/P|is composite. We now suppose that Upand U2pboth have primitive prime divisors. Since U2=P, it follows by Proposition 2.3 (iii) and Theorem 2.4 (viii) that N2=|U2p/P| is composite and thus is a super Lucas pseudoprime. Now consider the situation in which p≥11 and (p, P, Q)= (13,±1,2). It follows by Theorem 4.3 and Tables 1 and 3 of [3] that Up(P, Q) has a primitive divisor p1and U2p(P, Q) has a primitive divisor p2. We now see by our above argument that |U2p/P|is a super Lucas pseudoprime in this case. We finally suppose that p= 5 or 7 or it is the case that p= 13, P=±1, and Q= 2. By or discussion above, |U2p/P|is then a super Lucas pseudoprime if it is composite. We now observe by Theorem 4.3, Tables 1 and 3 of [3], and the proof of Theorem 3.1 of [10] that |U2p/P|is composite if it is not the case that (5.3) holds. Remark 5.4. In Theorem 2 of [7], Kiss showed that there is a constant Cdependent on Pand Qsuch that |U2p/P|is a super Lucas pseudoprime if p > C. In Theorem 5.3 above, we demonstrated that the constant Cis an absolute constant, not dependent on Pand Q, and that we can take C= 13. 6. Lucas Pseudoprimes of the Form Um(P, Q)orU2m(P, Q)/P Lemma 6.1 below will be a key tool in proving five of our main results, Theorems 6.2, 6.3, 6.5, 6.6, and 6.10.
INTEGERS: 25 (2025) 17 Lemma 6.1. Let U(P, Q)be a nondegenerate LSFK for which gcd(P, Q)=1and D > 0. Let m > 1be an odd integer such that gcd(m, PQD)=1, and 3∤mif P≡Q≡1 (mod 2). Let N1=Umand N2=U2m/P. Then N1and N2are both positive odd integers such that gcd(N1N2, PQD)=1. Further, if mis composite, then N1and N2are both composite. Moreover, (D/m) = (D/N1)=(D/N2)if any of the following three conditions are satisfied: (i) P≡1 (mod 2); (ii) P≡0 (mod 4) and Q≡ −1 (mod 4); (iii) P≡2 mod 4 and Q≡ −1 (mod 8). Proof. By Theorem 4.7, we can assume that P > 0. We note that P=U2and mis odd. It now follows by Theorem 2.4 (vii) and (ix), Lemmas 2.6, 2.7, 2.9, and 4.10 that both N1and N2are positive odd integers such that gcd(N1N2, PQD) = 1. By Corollary 4.2, N1and N2are both composite if mis composite. By (2.3), N1=Um(P, Q) = (m−1)/2 X k=0 m 2k+ 11 2m−1Pm−(2k+1)Dk =m1 2m−1Pm−1+m 31 2m−1Pm−3D+. . . +m m−21 2m−1P2D(m−3)/2+1 2m−1D(m−1)/2(6.1) and N2=U2m(P, Q)/P = m−1 X k=0 2m 2k+ 11 22m−1P2m−2k−2Dk =m1 22m−2P2m−2+2m 31 22m−1P2m−4D+. . . +2m 2m−31 22m−1P2Dm−2+1 22m−1Dm−1.(6.2) (i) Suppose that P≡1 (mod 2) and 3 ∤mif Q≡1 (mod 2). Then D= P2−4Q≡1 (mod 4). Then by (6.1) and (6.2), we obtain N1=Um≡m(2−1P)m−1(mod D) (6.3) and N2=U2m/P ≡m(2−1P)2(m−1) (mod D).(6.4) It now follows from (6.3), (6.4), Lemma 4.10, and the properties of the Jacobi symbol that (D/N1) = (N1/D) = (m/D)((2−1P)m−1/D) = (m/D)=(D/m)
INTEGERS: 25 (2025) 18 and (D/N2)=(N2/D) = (m/D)((2−1P)2(m−1)/D) = (m/D)=(D/m). (ii) Suppose that P≡0 (mod 4) and Q≡ −1 (mod 4). Let P= 4iand Q= 4j−1. Then D=P2−4Q= 16i2−16j+ 4 ≡4 (mod 16). Hence, D= 4D1, where D1≡1 (mod 4). It now follows from (6.1) and (6.2) that N1=Um≡m(2−1P)m−1(mod D1) and N2=U2m/P ≡m(2−1P)2(m−1) (mod D1). Since N1and N2are odd, we see by Lemma 4.10, (6.1), and (6.2) that (D/N1) = (4D1/N1) = (4/N1)(D1/N1)=(D1/N1) = (N1/D1) = (m/D1)((2−1P)m−1/D1)=(m/D1)=(D1/m) = (4/m)(D1/m) = (4D1/m) = (D/m) and (D/N2) = (4D1/N2) = (4/N2)(D1/N2)=(D1/N2) = (N2/D1) = (m/D1)((2−1P)2(m−1)/D1)=(m/D1) = (D1/m) = (4D1/m)=(D/m). (iii) Suppose that P≡2 (mod 4) and Q≡ −1 (mod 8). Let P= 4i+ 2 and Q= 8j−1. Then P2= 16(i2+i) + 4 ≡4 (mod 32) (6.5) and D=P2−4Q= 16(i2+i)−32j+ 8 ≡8 (mod 32). Therefore, D= 8D2,(6.6) where D2≡1 (mod 4). We observe by (6.1) and (6.2) that N1=Um≡m(2−1P)m−1(mod D2) (6.7) and N2=U2m/P ≡m(2−1P)2(m−1) (mod D2).(6.8) It now follows by (6.7), (6.8), and Lemma 4.10 that (D/N1) = (8D2/N1) = (2/N1)(4/N1)(D2/N1) = (2/N1)(D2/N1) = (2/N1)(N1/D2) = (2/N1)(m/D2)((2−1P)m−1/D2) = (2/N1)(m/D2) = (2/N1)(D2/m) = (2/N1)(4/m)(D2/m) = (2/N1)(4D2/m) (6.9)
INTEGERS: 25 (2025) 19 and (D/N2) = (8D2/N2) = (2/N2)(4/N2)(D2/N2) = (2/N2)(D2/N2) = (2/N2)(N2/D2) = (2/N2)(m/D2)((2−1P)2(m−1)/D2) = (2/N2)(m/D2) = (2/N2)(D2/m) = (2/N2)(4/m)(D2/m) = (2/N2)(4D2/m).(6.10) Inspecting U(P, Q) modulo 8 and making use of the fact that P2≡4 (mod 8), we find that λ(8) = 8 and the initial terms of U(P, Q) (mod 8) are 0,1, P, 5,6P, 5,3P, 1,4P≡0,1, P, . . . (mod 8).(6.11) From (6.11), we see that if m≡1 or 7 (mod 8),then N1=Um(P, Q)≡1 (mod 8), while if m≡3 or 5 (mod 8),then N1=Um(P, Q)≡5 (mod 8). It then follows by the properties of the Jacobi symbol that (2/m) = (2/N1).(6.12) We now see by (6.9), (6.12), and (6.6) that (D/N1) = (2/N1)(4D2/m) = (2/m)(4D2/m) = (8D2/m)=(D/m), as desired. We finish our proof by showing that (D/N2)=(D/m). Let m= 8r+s, where s∈ {1,3,5,7}. Then 2m= 16r+ 2s, where 2s∈ {2,6,10,14}. Since Q≡ −1 (mod 8), we have that Q≡ −1 (mod 16) or Q≡ −9 (mod 16). We first consider the case in which Q≡ −1 (mod 16). Examining U(P, Q) modulo 16 and making use of the fact that P2≡4 (mod 16), we find that λ(16) = 16 and the first 19 terms of U(P, Q) (mod 16) are U0≡0, U1≡1, U2≡P, U3≡5, U4≡6P, U5≡13, U6≡3P, U7≡9, U8≡12P, U9≡9, U10 ≡5P, U11 ≡13, U12 ≡2P, U13 ≡5, U14 ≡7P, U15 ≡1, U16 ≡8P≡0, U17 ≡1, U18 ≡P(mod 16).(6.13) It now follows from (6.13) that if Q≡ −1 (mod 16),then U2m≡sP (mod 16).(6.14)
INTEGERS: 25 (2025) 20 Since P≡2 (mod 4), we obtain from (6.14) that if Q≡ −1 (mod 16),then N2=U2m/P ≡s≡m(mod 8).(6.15) We now treat the case in which Q≡ −9 (mod 16). Inspecting U(P, Q) modulo 16, we see that λ(16) = 16 and the first 19 terms of U(P, Q) (mod 16) are U0≡0, U1≡1, U2≡P, U3≡13, U4≡6P, U5≡13, U6≡3P, U7≡1, U8≡12P, U9≡9, U10 ≡5P, U11 ≡5, U12 ≡2P, U13 ≡5, U14 ≡7P, U15 ≡9, U16 ≡8P≡0, U17 ≡1, U18 ≡P(mod 16).(6.16) We find by (6.16) that if Q≡ −9 (mod 16),then U2m≡sP (mod 16).(6.17) It now follows from (6.17) that if Q≡ −9 (mod 16),then N2=U2m/P ≡s≡m(mod 8).(6.18) By (6.15) and (6.18), we obtain that (2/m) = (2/N2).(6.19) We now observe by (6.10), (6.19), and (6.6) that (D/N2) = (2/N2)(4D2/m) = (2/m)(4D2/m) = (8D2/m)=(D/m). The proof is now complete. We are now ready for the proofs of Theorems 6.2 and 6.3, whose statements are given below. Theorem 6.2. Let U(P, Q)be a nondegenerate LSFK for which gcd(P, Q) = 1 and D > 0. Let m≥5be an odd prime or a Lucas pseudoprime of the second kind such that gcd(m, PQD) = 1 and 3∤mif P≡Q≡1 (mod 2). Let N1=Um. Suppose that N1is composite if mis an odd prime. Then N1is a strong Lucas pseudoprime if any of the following three conditions are satisfied: (i) P≡1 (mod 2); (ii) P≡0 (mod 4) and Q≡ −1 (mod 4); (iii) P≡2 (mod 4) and Q≡ −1 (mod 8). Proof. By Lemma 6.1, N1is a positive odd composite integer. Since mis odd, it will then follow from Corollary 3.15 that N1is a strong Lucas pseudoprime if we
INTEGERS: 25 (2025) 21 can show that N1is a Lucas pseudoprime. Noting that mis an odd prime or a Lucas pseudoprime of the second kind, we find that Um≡(D/m) (mod m).(6.20) We see by (6.20) that m|Um−(D/m).(6.21) It now follows by Proposition 2.3 (iii) and (6.21) that N1=Um|UN1−(D/m). It will then follow that N1is a Lucas pseudoprime if we can show that (D/m) = (D/N1).(6.22) However, (6.22) holds by Lemma 6.1. The proof is now established. Theorem 6.2 was proved in [22] for the case in which P > 0 and Pis odd. Theorem 6.3. Let U(P, Q)be a nondegenerate LSFK for which Q=±1. Then D > 0. Let m≥5be an odd prime or a Lucas pseudoprime of the second kind such that gcd(m, PD) = 1 and 3∤mif P≡1 (mod 2). Let N1=Um. Then gcd(N1, PD) = 1 and 3∤N1if P≡1 (mod 2). Suppose that N1is composite if mis an odd prime and Q=−1. Then N1is a strong Lucas pseudoprime and a Frobenius pseudoprime such that gcd(N1, PD) = 1 and 3∤N1if P≡Q≡1 (mod 2), if any of the following two conditions are satisfied: (i) P≡1 (mod 2); (ii) P≡0 (mod 2) and Q=−1. Proof. By Remark 2.2, D > 0. By Corollary 4.2 (i) and Theorem 5.1 (i), N1=Umis composite. It now follows from Theorem 6.2 that N1is a strong Lucas pseudoprime if (i) or (ii) holds. We see by Lemma 6.1 that gcd(N1, PD) = 1. We also see from Lemma 2.8 that 3 ∤N1if P≡1 (mod 2). Since Q=±1, it now follows from Theorem 3.19 that N1is also a Frobenius pseudoprime if (i) or (ii) holds. Theorem 6.3 was proved in [22] for the case in which P > 0 and Pis odd. Remark 6.4. Consider the nondegenerate LSFK U(P, Q), where Q=±1. Using Theorem 6.3, we can explicitly find infinitely many Frobenius pseudoprimes that are also strong Lucas pseudoprimes with parameters Pand Q. Let mbe a Lucas pseudoprime of the second kind such that gcd(m, PD) = 1 and 3 ∤mif P≡1 (mod 2). Let M1=Umand Mi+1 =UMifor i≥1. Then by Theorem 6.3, Miis a Frobenius pseudoprime for i≥1.
INTEGERS: 25 (2025) 22 Theorem 6.5. Let U(P, Q)be a nondegenerate LSFK for which gcd(P, Q) = 1 and D > 0. Let m≥5be an odd prime or a Frobenius pseudoprime such that gcd(m, PQD)=1and 3∤mif P≡Q≡1 (mod 2). Let N2=U2m/P . Then N2is a Lucas pseudoprime if any of the following three conditions are satisfied: (i) P≡1 (mod 2); (ii) P≡0 (mod 4) and Q≡ −1 (mod 4); (iii) P≡2 (mod 4) and Q≡ −1 (mod 8). Proof. By Lemma 6.1, N2is a positive odd composite integer. Since mis odd, it follows from Proposition 2.3 (vi) that P|Vm. By Proposition 2.3 (i), N2=U2m/P =UmVm/P. (6.23) Noting that mis an odd prime or a Frobenius pseudoprime such that gcd(m, D) = 1, we find that Um≡(D/m) (mod m) and Vm≡P(mod m).(6.24) Therefore, by (6.23) and (6.24), U2m/P =Um(Vm/P)≡(D/m)PP−1≡(D/m) (mod m).(6.25) Then by (6.25), m|U2m/P −(D/m) and 2 |U2m/P −(D/m),(6.26) because U2m/P is odd. Consequently, by (6.26), 2m|U2m/P −(D/m).(6.27) Therefore, by Proposition 2.3 (iii) and (6.27), N2=U2m/P |U2m|UN2−(D/m). To complete the proof, we need to show that (D/m) = (D/N2).(6.28) However, (6.28) holds by Lemma 6.1. Theorem 6.5 now follows. Theorem 6.5 was proved in [22] for the case in which P > 0 and Pis odd. Theorem 6.6 improves on Theorem 6.5 when Q=±1 by showing that in this case, U2m(P, Q)/P is a Lucas pseudoprime when mis an odd prime or a Lucas pseudoprime rather than requiring that mbe an odd prime or a Frobenius pseudoprime. As mentioned above in Remark 3.20, Theorem 6.11 below shows that there are infinitely many Lucas pseudoprimes that are not Frobenius pseudoprimes.
INTEGERS: 25 (2025) 23 Theorem 6.6. Let U(P, Q)be a nondegenerate LSFK for which Q=±1. Then D > 0. Let m≥5be an odd prime or a Lucas pseudoprime such that gcd(m, P D) = 1and 3∤mif P≡1 (mod 2). Let N2=U2m/P. Then gcd(N2, PD)=1and 3∤N2 if P≡1 (mod 2). Further, N2is a Lucas pseudoprime if either of the following two conditions is satisfied: (i) P≡1 (mod 2); (ii) P≡0 (mod 2) and Q=−1. Proof. By Remark 2.2, D > 0. By Corollary 4.2 (ii), N2=U2m/P is composite. Moreover, by Lemma 6.1, N2is a positive odd integer such that gcd(N2, PD) = 1. Since mis odd, it follows from Proposition 2.3 (vi) that P|Vm. By Proposition 2.3 (i), U2m/P =Um(Vm/P). To complete the proof, we need to show that UN2−(D/N2)≡0 (mod N2).(6.29) Let r=m−(D/m). Then ris even and by Proposition 2.3 (ii), U2 r+1 −UrUr+2 =Qr= 1.(6.30) Since mis an odd prime or a Lucas pseudoprime, Ur≡0 (mod m).(6.31) Thus, by (6.30) and (6.31), U2 r+1 ≡1 (mod m). Let pbe a prime such that pi∥mfor some i≥1. Then U2 r+1 ≡1 (mod pi).(6.32) Since there exist primitive roots modulo pi, we have that Ur+1 ≡ε(mod pi),(6.33) where ε∈(−1,1). Thus, by (6.33) and Lemma 2.5, Vr≡Ur+1V0≡εV0≡2ε(mod pi), Vr+1 ≡Ur+1V1≡εV1≡P ε (mod pi). (6.34) Therefore, by (6.30), (6.32), (6.33) and the recursion relation (1.1) defining both U(P, Q) and V(P, Q), we have that −QUr−1=Ur+1 −PUr≡ε−P·0≡ε(mod pi) (6.35)
INTEGERS: 25 (2025) 24 and −QVr−1=Vr+1 −PVr≡Pε −2Pε ≡ −Pε (mod pi).(6.36) Since −Q=±1, we see by (6.35) and (6.36) that Ur−1≡ −Qε (mod pi) and Vr−1≡PQε (mod pi).(6.37) Now suppose that (D/m) = 1. Since gcd(P, m) = 1, we see by (6.33), (6.34), and Proposition 2.3 (i) that N2=U2m/P =UmVm/P =Ur+1Vr+1/P ≡ε(εP )P−1 ≡ε2≡1≡(D/m) (mod pi).(6.38) Next suppose that (D/m)=−1. Then by (6.37), (6.38), and Proposition 2.3 (i), N2=U2m/P =UmVm/P =Ur−1Vr−1/P ≡(−Qε)(PQε)P−1 ≡ −Q2ε2≡ −1≡(D/m) (mod pi).(6.39) Thus, by (6.38) and (6.39), N2−(D/m)≡0 (mod pi),(6.40) whether (D/m) = 1 or (D/m)=−1 for an arbitrary prime psuch that pi∥m. Therefore, it follows by (6.40) that N2−(D/m)≡0 (mod m).(6.41) Since N2is odd, we also see that N2−(D/m)≡0 (mod 2).(6.42) Noting that mis odd, we find by (6.41) and (6.42) that N2−(D/m)≡0 (mod 2m).(6.43) Since 2m|N2−(D/m) by (6.43), we see by Proposition 2.3 (iii) that N2=U2m/P |U2m|UN2−(D/m). It will now follow by (6.29) that N2is a Lucas pseudoprime if we can show that (D/m) = (D/N2).(6.44) However, (6.44) holds by Lemma 6.1.
INTEGERS: 25 (2025) 25 Remark 6.7. Let U(P, Q) be a nondegenerate Lucas sequence with discriminant D, where Q=±1. Suppose further that either it is the case that P≡1 (mod 2) or it is the case that P≡0 (mod 2) and Q=−1. By Theorem 6.6 and by Theorem 6.11 below, there in fact exist infinitely many Lucas pseudoprimes M′ with parameters Pand ±1 such that gcd(M′, PD) = 1, 3 ∤M′if P≡1 (mod 2), and M′is not a Frobenius pseudoprime. Given a Lucas pseudoprime M′ 1such that gcd(M′, PD) = 1 and 3 ∤M′ 1if P≡1 (mod 2), we can use Theorem 6.6 to explicitly find infinitely many other Lucas pseudoprimes M′ iwith parameters Pand Q=±1. Let M′ i+1 =1 PU2M′ ifor i≥1. Then M′ 2, M′ 3, M′ 4,..., are also Lucas pseudoprimes Nwith parameters Pand Q. Example 6.8. Consider the Fibonacci sequence U(1,−1). We observe by Tables 1 and 5 of [16] that there are 155 Lucas pseudoprimes less than 1 000 000, of which 56 are also Frobenius pseudoprimes. The first 10 Lucas pseudoprimes less than 1 000 000 which are not Frobenius pseudoprimes are 323,377,1891,3827,6601,8149,11663,13981,17119,17711. Theorem 6.9. Consider the LSFK U(P, Q), where Q=±1. Let Nbe a Lucas pseudoprime such that gcd(N, D)=1and Nis not a strong Lucas pseudoprime. Suppose that 2k∥ρ(N). Then we have: (i) If Q=−1, then Nis a Frobenius pseudoprime if and only if N≡(D/N) (mod 2k+1)and (D/N) = 1; (ii) If Q= 1, then Nis a Frobenius pseudoprime if and only if N≡(D/N) (mod 2k+1). This is proved in Theorem 3.2 of [22]. Theorem 6.10. Consider the nondegenerate LSFK U(P, Q), where Q=±1. Then D > 0. Let m≥5be an odd prime or a Lucas pseudoprime such that gcd(m, P D) = 1and 3∤mif Pis odd. Let N2=U2m/P. Suppose that either P≡1 (mod 2) or it is the case that P≡0 (mod 2) and Q=−1. Then N2is a Lucas pseudoprime. Moreover, the following hold: (i) Suppose that Pis odd and Q=−1. Then N2is a Frobenius pseudoprime if and only if m≡(D/m) (mod 6) and (D/m) = 1. (ii) Suppose that Pis odd and Q= 1. Then N2is a Frobenius pseudoprime if and only if m≡(D/m) (mod 6). (iii) Suppose that P≡0 (mod 2) and Q=−1. Then N2is a Frobenius pseudoprime if and only if m≡(D/m) (mod 4) and (D/m) = 1.
INTEGERS: 25 (2025) 32 [6] P. Hilton, J. Pedersen, L. Somer, On Lucasian numbers, Fibonacci Quart. 35 (1997), 43–47. [7] P. Kiss, Some results on Lucas pseudoprimes, Ann. Univ. Sci. Budapest. E˝otv˝os Sect. Math. 28 (1985), 153–159. [8] M. Kˇr´ıˇzek, L. Somer, A. ˇ Solcov´a, From great discoveries in number theory to applications, Springer, Cham, 2021. [9] D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. 31 (1930), 419–448. [10] F. Luca, L. Somer, Lucas sequences for which 4 |ϕ(|un|) for almost all n,Fibonacci Quart. 44 (2006), 249–263. [11] C. Pomerance, J. L. Selfridge, S. S. Wagstaff, Jr., The pseudoprimes to 25 ·109,Math. Comp. 35 (1980), 1003–1026. [12] P. Ribenboim, The New Book of Prime Number Records, Springer, New York, 1996. [13] A. Rotkiewicz, On Lucas numbers with two intrinsic divisors, Bull. Acad. Polon. Sci. S´er. Sci. Math. Astronom. Phys. 10 (1962), 223–232. [14] A. Rotkiewicz, On the pseudoprimes with respect to the Lucas sequence, Bull. Acad. Polon. Sci. S´er. Sci. Math. Astronom. Phys. 21 (1973), 793–797. [15] A. Rotkiewicz, Lucas pseudoprimes, Funct. Approx. Comment. Math. 28 (2000), 97–104. [16] A. Rotkiewicz, Lucas and Frobenius pseudoprimes, Ann. Math. Sil. 17 (2003), 17–39. [17] A. Schinzel, On primitive prime factors of Lehmer numbers I, Acta Arith. 8(1963), 213–223. [18] L. Somer, Generalization of a theorem of Drobot, Fibonacci Quart. 40 (2002), 435–437. [19] L. Somer, Lucas sequences Ukfor which U2pand U2pare pseudoprimes for almost all primes p, Fibonacci Quart. 44 (2006), 7–12. [20] L. Somer, M. Kˇr´ıˇzek, Prime Lehmer and Lucas numbers with composite indices, Fibonacci Quart. 51 (2013), 194–214. [21] L. Somer, M.Kˇr´ıˇzek, On primes in Lucas sequences, Fibonacci Quart. 53 (2015), 2–23. [22] L. Somer, M. Kˇr´ıˇzek, Frobenius, Lucas, and Dickson pseudoprimes, Fibonacci Quart. 60 (2022), 325–343. [23] M. Ward, Prime divisors of second order recurring sequences, Duke Math. J. 21 (1954), 607–614. [24] mathworld.wolfram.com/FibonacciPrime.html