On Lucas and Frobenius Pseudoprimes}

#A107 INTEGERS 25 (2025)
ON LUCAS AND FROBENIUS PSEUDOPRIMES
Law ence Some
Depa men o Ma hema ics, Ca holic Uni e si y o Ame ica, Washing on, D.C.
[email p o ec ed]
Michal Kˇ ´ıˇzek
Ins i u e o Ma hema ics, Czech Academy o Sciences, P ague, Czech Republic
[email p o ec ed]
Recei ed: 12/30/24, Re ised: 5/22/25, Accep ed: 11/3/25, Published: 11/25/25
Abs ac
Conside he Lucas sequences U(P, Q) and V(P, Q) which sa is y he linea ecu -
ence ela ion Wn+2 =PWn+1−QWnwi h ini ial e ms U0= 0, U1= 1, and V0= 2,
V1=P, espec i ely, whe e Pand Qa e in ege s. We conside pseudop imes wi h
pa ame e s Pand Q ela ed o U(P, Q) and V(P, Q). We ex end esul s ob ained by
Some and Kˇ ´ıˇzek (2022) ega ding pseudop imes wi h pa ame e s Pand Q, whe e
Pis odd and g ea e han 0 o hose in which he pa ame e Pcan also be less han
0 o e en. We also ob ain in ini ely many new examples o pseudop imes, called
he Lucas pseudop imes wi h pa ame e s Pand Q. We u he p esen esul s on
F obenius pseudop imes, which a e gene aliza ions o Lucas pseudop imes.
– Dedica ed o P o esso Cu is Coope on he occasion o his e i emen .
1. In oduc ion
Le Pand Qbe in ege numbe s. Le U(P, Q), called he Lucas sequence o he i s
kind (LSFK), and V(P, Q), called he Lucas sequence o he second kind (LSSK),
be he sequences sa is ying he linea ecu sion ela ion
Wn+2 =PWn+1 −QWn(n≥0) (1.1)
wi h disc iminan D=P2−4Qand he ini ial e ms W0and W1a e U0= 0, U1= 1
and V0= 2, V1=P, espec i ely.
In his pape , we will ex end esul s ob ained by Some and Kˇ ´ıˇzek [22] conce ning
pseudop imes ela ed o he Lucas sequences U(P, Q) and V(P, Q). These esul s
a e gene alized om pseudop imes wi h pa ame e s Pand Q o which Pis g ea e
DOI: 10.5281/zenodo.17711594
INTEGERS: 25 (2025) 2
han 0 and odd o addi ional cases in which Pcan also be less han 0 o e en. We
will also ob ain in ini ely many new cases o one ype o pseudop ime de ined below
in De ini ion 3.1, called he Lucas pseudop imes wi h pa ame e s Pand Q. We also
discuss F obenius pseudop imes which a e gene aliza ions o Lucas pseudop imes.
2. Necessa y De ini ions and Resul s
To p oceed, we will equi e he ollowing de ini ions and esul s. I mis a posi i e
in ege , i is easily seen ha U(P, Q) and V(P, Q) a e pu ely pe iodic modulo
mwhen gcd(m, Q) = 1 (see [5, pp. 344–345]). F om he e on, we assume ha
gcd(m, Q) = 1. Th oughou his pape , pand pideno e p imes and malways
ep esen s a posi i e in ege . We deno e he pe iod o U(P, Q) modulo mby λ(m),
ha is, λ(m) is he leas posi i e in ege ssuch ha
Us+n≡un(mod m)
o all n≥0. The ank o appea ance o min U(P, Q), deno ed by ρ(m), is he
leas posi i e in ege such ha
U ≡0 (mod m).
Since U0= 0 and U(P, Q) is pu ely pe iodic modulo m, we see ha ρ(m) exis s.
I is clea ha U ≡0 (mod m) i and only i ρ(m)| . The p ime pis called a
p imi i e p ime di iso o Un(P, Q)i ρ(p)=n. Equi alen ly, pis a p imi i e p ime
di iso o Un(P, Q) i p|Un(P, Q), bu p∤Ui(P, Q) o 1 ≤i≤n−1.
Associa ed wi h U(P, Q) and V(P, Q) is he cha ac e is ic polynomial
(x) = x2−Px +Q
wi h disc iminan D=D(P, Q)=P2−4Qand cha ac e is ic oo s
α= (P+√D)/2 and β= (P−√D)/2.(2.1)
We obse e ha
D= (α−β)2.(2.2)
I ollows om (2.1), (2.2), he Bine o mulas, and he binomial o mula ha
Un(P, Q) = αn−βn
√D=
⌊(n−1)/2⌋
X
k=0 n
2k+ 11
2n−1Pn−(2k+1)Dk(2.3)
and
Vn(P, Q)=αn+βn=
⌊n/2⌋
X
k=0 n
2k1
2n−1Pn−2kDk.(2.4)
INTEGERS: 25 (2025) 3
The Lucas sequences U(P, Q) and V(P, Q) wi h cha ac e is ic oo s αand βa e
called degene a e i PQ = 0 o α/β is a oo o uni y. I ollows om he Bine
o mulas (2.3) and (2.4) ha Un(P, Q)o Vn(P, Q) can be equal o 0 o some n > 0
only i U(P, Q) and V(P, Q) a e degene a e. Since he cha ac e is ic polynomial o
U(P, Q) and V(P, Q) is a quad a ic polynomial wi h in ege coe icien s, one sees
ha α/β can be a p imi i e n h oo o uni y only i n∈ {1,2,3,4,6}. The ollowing
heo em de e mines all degene a e Lucas sequences U(P, Q) and V(P, Q).
Theo em 2.1. Le Mdeno e an a bi a y nonze o in ege . Then he Lucas se-
quences U(P, Q)and V(P, Q)wi h cha ac e is ic oo s αand βa e degene a e only
in he ollowing cases:
(i) Q= 0,Pis any in ege . Then D=P2,Un=Pn−1, and Vn=Pn o n≥1.
(ii) α/β = 1. Then P= 2M,Q=M2, and D= 0.
(iii) α/β =−1. Then P= 0,Q=M, and D=−4M.
(i ) α/β is a p imi i e cube oo o uni y. Then P=M,Q=M2, and D=
−3M2.
( ) α/β is a p imi i e ou h oo o uni y. Then P= 2M,Q= 2M2, and
D=−4M2.
( i) α/β is a p imi i e six h oo o uni y. Then P= 3M,Q= 3M2, and D=
−3M2.
This is p o ed in [23, p. 613].
Rema k 2.2. Conside he nondegene a e LSFK U(P, Q), whe e Q=±1. We
no e ha by Theo em 2.1, D=P2−4Q>0.
The ollowing P oposi ion 2.3, Theo em 2.4, Lemmas 2.5–2.9, and Co olla y 2.10
will be needed o he p oo o ou p incipal esul s.
P oposi ion 2.3. Conside he nondegene a e Lucas sequences U(P, Q)and V(P, Q).
Then he ollowing hold:
(i) U2n=UnVn;
(ii) U2
n+1 −UnUn+2 =Qn;
(iii) i m|n, hen Um|Un;
(i ) i m|nand n/m is odd, hen Vm|Vn;
( ) P|U2n o all n≥0;
INTEGERS: 25 (2025) 4
( i) P|Vn o nodd;
( ii) Un(−P, Q)=(−1)n+1Un(P, Q);
( iii) Vn(−P, Q)=(−1)nVn(P, Q).
P oo . Pa s (i)–(i ) and ( ii)–( iii) ollow om he Bine o mulas (2.3) and (2.4).
Pa ( ) ollows om pa (iii) and pa ( i) ollows om pa (i ) upon no ing ha
U2=V1=P.
Theo em 2.4. Conside he LSFK U(P, Q)and he LSSK V(P, Q)wi h disc imi-
nan D. Le and sbe posi i e in ege s.
(i) I gcd( , Q)=1, hen |Usi and only i ρ( )|s;
(ii) i pis an odd p ime and p∤Q, hen p|Up−(D/p), whe e (D/p)is he Legend e
symbol and (D/p)=0i p|D;
(iii) i p|Dand p∤Q, hen ρ(p) = p;
(i ) i p∤2QD, hen U(p−(D/p))/2i and only i (Q/p) = 1;
( ) i p∤Q,ρ(pk)=ρ(p), and ρ(pk+1)=ρ(p), hen ρ(pj) = pmax(j−k,0)ρ(p) o
j≥1;
( i) i gcd( s, Q) = 1 and |s, hen ρ( )|ρ(s);
( ii) i gcd(P, Q)=1and d= gcd( , s), hen gcd(U , Us)=|Ud|;
( iii) i gcd( , s) = gcd( s, Q)=1, hen ρ( s) = lcm(ρ( ), ρ(s));
(ix) i gcd(P, Q)=1and p|Q, hen p∤Un o n≥1;
(x) i gcd(P, Q)=1, hen p≡(D/p) (mod ρ(p)).
This ollows om he esul s in [12, pp. 53–74], [4], and [9].
Lemma 2.5. Conside he LSFK U(P, Q), whe e Q= 0. Le W(P, Q)be a ecu -
ence sa is ying he ecu sion ela ion (1.1) wi h ini ial e ms W0and W1. Suppose
ha U ≡0 (mod m), whe e gcd(m, Q)=1. Then
Wn+ ≡U +1Wn(mod m)
o all n≥0.
INTEGERS: 25 (2025) 5
P oo . I can be shown by induc ion and use o he linea ecu sion ela ion de ining
bo h U(P, Q) and W(P, Q) ha
Wn+s=−QWn−1Us+WnUs+1.
Thus,
Wn+ ≡ −QWn−1U +WnU +1 ≡ −QWn−1·0 + WnU +1 ≡U +1Wn(mod m)
o all n≥0.
Lemma 2.6. Conside he Lucas sequence U(P, Q), whe e gcd(P, Q) = 1. Le pbe
a p ime such ha pi∥U2=P, whe e pi∥U2means ha pi|U2, bu pi+1 ∤U2.
Le nbe a posi i e in ege . Then pi+1 |U2ni and only i p|n. In pa icula ,
gcd(U2n/P, P)=1i gcd(n, P ) = 1.
P oo . This ollows om Theo em X o [4].
Lemma 2.7. Le U(P, Q)be a Lucas sequence o which 2∤gcd(P, Q).
(i) U(P, Q)is pu ely pe iodic modulo 2.
(ii) Suppose Pis odd and Qis e en. Then 2∤Un o n≥1.
(iii) Suppose Pis e en and Qis odd. Then 2|Uni and only 2|n. Mo eo e ,
2|D.
(i ) Suppose Pand Qa e bo h odd. Then 2|Uni and only 3|n.
P oo . This ollows by inspec ion o U(P, Q) modulo 2.
Lemma 2.8. Le U(P, Q)be a Lucas sequence o which 3∤gcd(P, Q).
(i) U(P, Q)is pu ely pe iodic modulo 3.
(ii) I 3|Q, hen 3∤Un o n≥1.
(iii) I 3|P, hen ρ(3) = 2 and 3|Uni and only i 2|n.
(i ) I 3∤Pand Q≡ −1 (mod 3), hen ρ(3) = 4 and 3|Uni and only i 4|n.
( ) I 3∤Pand Q≡1 (mod 3), hen ρ(3) = 3 and 3|Uni and only i 3|n.
Mo eo e , 3|D.
P oo . This ollows by inspec ion o U(P, Q) modulo 3.
Lemma 2.9. Le U(P, Q)and V(P, Q)be nondegene a e Lucas sequences such ha
D > 0. Then |Un|is inc easing o n≥2and |Vn|is inc easing o n≥1. Fu he ,
i P > 0, hen Un>0 o n≥1and Vn>0 o n≥0. Mo eo e , i i is no he
case ha |P|=−Q= 1, hen |U3|≥3.

INTEGERS: 25 (2025) 6
This ollows om Lemma 3 o [6] and Lemma 2.8 o [10].
The ollowing co olla y is immedia e om Lemma 2.9.
Co olla y 2.10. Le U(P, Q)be a nondegene a e LSFK such ha D > 0. Then
ρ(Un)=n o n≥3.
3. Pseudop imes Rela ed o he Lucas Sequences U(P, Q) and V(P, Q)
I ollows om Theo em 2.4 (ii) and (i ) and he Bine o mulas (2.3) and (2.4)
ha i Nis an odd p ime such ha gcd(N, PQD) = 1, hen he ollowing ou
cong uences a e all sa is ied o he Lucas sequences U(P, Q) and V(P, Q) wi h
disc iminan D, whe e (D/N) deno es he 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)
I also occu s a ely ha a leas one o he ou cong uences (3.1)–(3.4) holds i
Nis a posi i e odd composi e in ege . We no e ha by [2, p. 1392], any wo o he
ou cong uences abo e imply he o he wo when Nis a posi i e odd in ege . We
ha e he ollowing de ini ions which a e gi en in [16].
De ini ion 3.1. The posi i e odd composi e in ege Nis called a Lucas pseudo-
p ime wi h pa ame e s Pand Qi gcd(N, QD) = 1 and cong uence (3.1) holds.
(We simply deno e Nas a Lucas pseudop ime i he pa ame e s Pand Qa e un-
de s ood.)
De ini ion 3.2. The posi i e odd composi e in ege Nis called a Lucas pseudo-
p ime o he second kind wi h pa ame e s Pand Qi gcd(N, QD) = 1 and cong u-
ence (3.2) holds.
De ini ion 3.3. The posi i e odd composi e in ege Nis called a Dickson pseudo-
p ime wi h pa ame e s Pand Qi gcd(N, QD) = 1 and cong uence (3.3) holds.
De ini ion 3.4. The posi i e odd composi e in ege Nis called a Dickson pseudo-
p ime o he second kind wi h pa ame e s Pand Qi gcd(N, QD) = 1 and cong u-
ence (3.4) holds.
Fo pa icula pai s o pa ame e s Pand Qi is known ha he e exis in ini ely
many odd composi e in ege s N ha sa is y each o he cong uences (3.1)–(3.4) (see
Theo em 1 o [14]). This gi es ise o he ollowing de ini ion appea ing in [16].
INTEGERS: 25 (2025) 7
De ini ion 3.5. The posi i e odd composi e in ege Nis called a F obenius pseu-
dop ime wi h pa ame e s Pand Qi gcd(N, PQD) = 1 and cong uences (3.1)–(3.4)
all hold.
In [22] we ound amilies o Lucas pseudop imes and F obenius pseudop imes wi h
pa ame e s Pand Qin which P > 0 and Pis odd. In his pape , we will gene alize
hese esul s by emo ing he es ic ion on Pand allowing nega i e alues o P
as well as pe mi ing P o be e en. In bo h his pape and [22], we gi e special
a en ion o he si ua ion in which Q=±1.
In addi ion, he de ini ions o he i e ypes o pseudop imes gi en below will be
needed o ou u he wo k.
De ini ion 3.6. Le Nbe a posi i e odd composi e in ege and le abe a posi i e
odd in ege such ha gcd(a, N) = 1. Then Nis called a pseudop ime o he base a
i
an−1≡1 (mod N).
De ini ion 3.7. Le Nbe a posi i e odd composi e in ege and le abe a posi i e
odd in ege such ha gcd(a, N) = 1. Then Nis called an Eule pseudop ime o he
base ai
a(N−1)/2≡1 (mod N) i (a/N) = 1
o
a(N−1)/2≡ −1 (mod N) i (a/N)=−1.
I is clea ha Nis a pseudop ime o he base ai Nis an Eule pseudop ime
o he base a.
Rema k 3.8. Le Nbe a posi i e odd in ege and le Q=±1. Then by he
p ope ies o he Jacobi symbol,
Q(N−1)/2= (Q/N),
and Nis always an Eule pseudop ime o he base Q.
De ini ion 3.9. Conside he LSFK U(P, Q) and he LSSK V(P, Q). The posi i e
odd composi e in ege Nis called an Eule –Lucas pseudop ime wi h pa ame e s P
and Qi gcd(N, QD) = 1 and
U(N−(D/N))/2≡0 (mod N) i (Q/N) = 1
o
V(N−(D/N))/2≡0 (mod N) i (Q/N) = −1.
De ini ion 3.10. Conside he LSFK U(P, Q) and he LSSK V(P, Q). Le Nbe
a posi i e odd composi e in ege such ha gcd(N, QD) = 1 and N−(D/N)=2sd,
whe e dis odd. Then Nis called a s ong Lucas pseudop ime wi h pa ame e s P
and Qi ei he
INTEGERS: 25 (2025) 8
(i) Ud≡0 (mod N), o
(ii) V2 d≡0 (mod N) o some wi h 0 ≤ < s.
Rema k 3.11. I ollows om P oposi ion 2.3 (i) and (iii) ha Eule –Lucas pseu-
dop imes and s ong Lucas pseudop imes a e Lucas pseudop imes.
Theo em 3.12. Conside he LSFK U(P, Q). Le Nbe a posi i e odd composi e
in ege Nsuch ha gcd(N, QD) = 1. I Nis a s ong Lucas pseudop ime, hen N
is an Eule –Lucas pseudop ime.
This is p o ed in Theo em 3 o [2].
De ini ion 3.13. The posi i e odd composi e in ege Nis called a supe Lucas
pseudop ime wi h pa ame e s Pand Qi gcd(N, QD) = 1 and each di iso o N
g ea e han 1 is a p ime o a Lucas pseudop ime wi h pa ame e s Pand Q.Supe
F obenius pseudop imes and supe s ong Lucas pseudop imes wi h pa ame e s P
and Qa e de ined simila ly.
Theo ems 3.14 and 3.16 gi en below p o ide necessa y and su icien c i e ia o
an odd composi e in ege N o be a s ong Lucas pseudop ime o a supe Lucas
pseudop ime.
Theo em 3.14. Conside he nondegene a e LSFK U(P, Q). Le
N=
s
Y
i=1
pki
i
be an odd composi e in ege such ha gcd(N, PQD)=1. Suppose ha Nis a
Lucas pseudop ime. Then ρ(pki
i)=pi o 1≤i≤s. I Nis also a s ong Lucas
pseudop ime, hen ν2(ρ(pi))=ν2(ρ(pj)) o 1≤i<j≤s, whe e ν2(m)=ii
pi|m, bu pi+1 ∤m.
Con e sely, i Nis a Lucas pseudop ime such ha ν2(ρ(pi))=ν2(ρ(pj)) o
1≤i<j≤s, hen Nis in addi ion a s ong Lucas pseudop ime.
This is p o ed in P oposi ion 2.18 o [22].
Co olla y 3.15. Conside he nondegene a e LSFK U(P, Q). Le Nbe a Lucas
pseudop ime o which gcd(N, QD) = 1. Then, Nis in addi ion a s ong Lucas
pseudop ime i ρ(N)is odd.
P oo . By Theo em 2.4 ( i), i p|N, hen ρ(p)|ρ(N). The esul now ollows om
Theo em 3.14.
INTEGERS: 25 (2025) 9
Theo em 3.16. Conside he nondegene a e LSFK U(P, Q). Le p1, p2, . . . , psbe
dis inc odd p imes each ela i ely p ime o QD such ha ρ(pmi
i) = ρ(pi), bu
ρ(pmi+1
i)=ρ(pi) o i∈ {1, . . . , s}. Le
h= lcm(ρ(p1), ρ(p2), . . . , ρ(ps)).
Le Nbe an odd composi e in ege such ha
N=
s
Y
i=1
pki
i,
whe e 1≤ki≤mi. Then ρ(N)=hand Nis a supe Lucas pseudop ime i and
only i o each i= 1,...,s,
pi≡(D/pi) (mod h).
This is p o ed in Theo em 2.22 o [22].
Theo em 3.17. Conside he nondegene a e LSFK U(P, Q). Le
N=
s
Y
i=1
pki
i
be an odd composi e in ege such ha gcd(N, PQD) = 1. Suppose ha
ρ(pki
i)=ρ(pi) = ρ(pkj
j)=ρ(pj) o 1 ≤i < j ≤s.
Then Nis a supe s ong Lucas pseudop ime. Addi ionally, i Q=±1, hen Nis
also a supe F obenius pseudop ime.
This ollows om he p oo o P oposi ion 2.23 in [22].
Theo em 3.18. Conside he nondegene a e LSFK U(P, Q). Suppose ha Nis
an Eule –Lucas pseudop ime wi h pa ame e s Pand Qand ha Nis also an Eule
pseudop ime o he base Q, whe e gcd(N, PQD) = 1. Then Nis a F obenius
pseudop ime.
This is p o ed in Theo em 1 o [15].
Theo em 3.19. Conside he nondegene a e LSFK U(P, Q), whe e Q=±1. Sup-
pose ha Nis a posi i e odd composi e in ege such ha gcd(N, P D) = 1. I Nis
a s ong Lucas pseudop ime, hen Nis a F obenius pseudop ime.
P oo . By Theo em 3.12, Nis also an Eule –Lucas pseudop ime wi h pa ame e s
Pand Q. By Rema k 3.8, Nis mo eo e an Eule pseudop ime o he base Q. I
now ollows om Theo em 3.18 ha Nis a F obenius pseudop ime.
INTEGERS: 25 (2025) 16
pseudop ime i i is no he case ha (p, P, Q) = (5,±1,2) o (5,±1,3) o (5,±2,3)
o (5,±12,55) o (13,±1,2). Mo eo e ,
|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 a e all p imes.
P oo . By P oposi ion 2.3 ( ), P|U2p. We no e ha U1= 1, U2=P, and
gcd(p, P) = 1. I hen ollows om Lemma 2.6, P oposi ion 2.3 (iii), and Theo em
2.4 (i) ha he only p ime di iso s o N2=|U2p/P|a e he p imi i e p ime di iso s
o Upand U2p. We now show ha i |U2p/P |is composi e, hen N2=|U2p/P|is a
supe Lucas pseudop ime. Since N2|U2p, i ollows ha ρ(N2)|2p. Suppose ha
q1is a p imi i e p ime di iso o Up. By Theo em 2.4 (ii), (iii), and (x), q1≡(D/q1)
(mod p), whe e (D/q1)=±1, since p∤D. As q1−(D/q1) is e en and pis odd, i
ollows ha q1≡(D/q1) (mod 2p). Fu he by Theo em 2.4 (ii), (iii), and (x), i q2
is a p imi i e p ime di iso o U2p, hen q2≡(D/q2) (mod 2p), whe e (D/q2)=±1,
since 2p=ρ(q2) is no a di iso o D. We now see by Theo em 3.16 ha N2is a
supe Lucas pseudop ime i |U2p/P|is composi e.
We now suppose ha Upand U2pbo h ha e p imi i e p ime di iso s. Since
U2=P, i ollows by P oposi ion 2.3 (iii) and Theo em 2.4 ( iii) ha N2=|U2p/P|
is composi e and hus is a supe Lucas pseudop ime. Now conside he si ua ion in
which p≥11 and (p, P, Q)= (13,±1,2). I ollows by Theo em 4.3 and Tables 1
and 3 o [3] ha Up(P, Q) has a p imi i e di iso p1and U2p(P, Q) has a p imi i e
di iso p2. We now see by ou abo e a gumen ha |U2p/P|is a supe Lucas
pseudop ime in his case.
We inally suppose ha p= 5 o 7 o i is he case ha p= 13, P=±1, and
Q= 2. By o discussion abo e, |U2p/P|is hen a supe Lucas pseudop ime i i is
composi e. We now obse e by Theo em 4.3, Tables 1 and 3 o [3], and he p oo
o Theo em 3.1 o [10] ha |U2p/P|is composi e i i is no he case ha (5.3)
holds.
Rema k 5.4. In Theo em 2 o [7], Kiss showed ha he e is a cons an Cdepen-
den on Pand Qsuch ha |U2p/P|is a supe Lucas pseudop ime i p > C. In
Theo em 5.3 abo e, we demons a ed ha he cons an Cis an absolu e cons an ,
no dependen on Pand Q, and ha we can ake C= 13.
6. Lucas Pseudop imes o he Fo m Um(P, Q)o U2m(P, Q)/P
Lemma 6.1 below will be a key ool in p o ing i e o ou main esul s, Theo ems
6.2, 6.3, 6.5, 6.6, and 6.10.

INTEGERS: 25 (2025) 17
Lemma 6.1. Le U(P, Q)be a nondegene a e LSFK o which gcd(P, Q)=1and
D > 0. Le m > 1be an odd in ege such ha gcd(m, PQD)=1, and 3∤mi
P≡Q≡1 (mod 2). Le N1=Umand N2=U2m/P. Then N1and N2a e bo h
posi i e odd in ege s such ha gcd(N1N2, PQD)=1. Fu he , i mis composi e,
hen N1and N2a e bo h composi e. Mo eo e , (D/m) = (D/N1)=(D/N2)i any
o he ollowing h ee condi ions a e sa is ied:
(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).
P oo . By Theo em 4.7, we can assume ha P > 0. We no e ha P=U2and mis
odd. I now ollows by Theo em 2.4 ( ii) and (ix), Lemmas 2.6, 2.7, 2.9, and 4.10
ha bo h N1and N2a e posi i e odd in ege s such ha gcd(N1N2, PQD) = 1. By
Co olla y 4.2, N1and N2a e bo h composi e i mis composi e. By (2.3),
N1=Um(P, Q) =
(m−1)/2
X
k=0 m
2k+ 11
2m−1Pm−(2k+1)Dk
=m1
2m−1Pm−1+m
31
2m−1Pm−3D+. . .
+m
m−21
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+ 11
22m−1P2m−2k−2Dk
=m1
22m−2P2m−2+2m
31
22m−1P2m−4D+. . .
+2m
2m−31
22m−1P2Dm−2+1
22m−1Dm−1.(6.2)
(i) Suppose ha P≡1 (mod 2) and 3 ∤mi Q≡1 (mod 2). Then D=
P2−4Q≡1 (mod 4). Then by (6.1) and (6.2), we ob ain
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)
I now ollows om (6.3), (6.4), Lemma 4.10, and he p ope ies o he Jacobi
symbol ha
(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 ha P≡0 (mod 4) and Q≡ −1 (mod 4). Le P= 4iand Q=
4j−1. Then
D=P2−4Q= 16i2−16j+ 4 ≡4 (mod 16).
Hence, D= 4D1, whe e D1≡1 (mod 4). I now ollows om (6.1) and (6.2) ha
N1=Um≡m(2−1P)m−1(mod D1)
and
N2=U2m/P ≡m(2−1P)2(m−1) (mod D1).
Since N1and N2a e odd, we see by Lemma 4.10, (6.1), and (6.2) ha
(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 ha P≡2 (mod 4) and Q≡ −1 (mod 8). Le 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).
The e o e,
D= 8D2,(6.6)
whe e D2≡1 (mod 4). We obse e by (6.1) and (6.2) ha
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)
I now ollows by (6.7), (6.8), and Lemma 4.10 ha
(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)
Inspec ing U(P, Q) modulo 8 and making use o he ac ha P2≡4 (mod 8), we
ind ha λ(8) = 8 and he ini ial e ms o U(P, Q) (mod 8) a e
0,1, P, 5,6P, 5,3P, 1,4P≡0,1, P, . . . (mod 8).(6.11)
F om (6.11), we see ha
i m≡1 o 7 (mod 8), hen N1=Um(P, Q)≡1 (mod 8),
while
i m≡3 o 5 (mod 8), hen N1=Um(P, Q)≡5 (mod 8).
I hen ollows by he p ope ies o he Jacobi symbol ha
(2/m) = (2/N1).(6.12)
We now see by (6.9), (6.12), and (6.6) ha
(D/N1) = (2/N1)(4D2/m) = (2/m)(4D2/m) = (8D2/m)=(D/m),
as desi ed.
We inish ou p oo by showing ha (D/N2)=(D/m). Le
m= 8 +s, whe e s∈ {1,3,5,7}.
Then
2m= 16 + 2s, whe e 2s∈ {2,6,10,14}.
Since Q≡ −1 (mod 8), we ha e ha Q≡ −1 (mod 16) o Q≡ −9 (mod 16).
We i s conside he case in which Q≡ −1 (mod 16). Examining U(P, Q) modulo
16 and making use o he ac ha P2≡4 (mod 16), we ind ha λ(16) = 16 and
he i s 19 e ms o U(P, Q) (mod 16) a e
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)
I now ollows om (6.13) ha
i Q≡ −1 (mod 16), hen U2m≡sP (mod 16).(6.14)
INTEGERS: 25 (2025) 20
Since P≡2 (mod 4), we ob ain om (6.14) ha
i Q≡ −1 (mod 16), hen N2=U2m/P ≡s≡m(mod 8).(6.15)
We now ea he case in which Q≡ −9 (mod 16). Inspec ing U(P, Q) modulo
16, we see ha λ(16) = 16 and he i s 19 e ms o U(P, Q) (mod 16) a e
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 ind by (6.16) ha
i Q≡ −9 (mod 16), hen U2m≡sP (mod 16).(6.17)
I now ollows om (6.17) ha
i Q≡ −9 (mod 16), hen N2=U2m/P ≡s≡m(mod 8).(6.18)
By (6.15) and (6.18), we ob ain ha
(2/m) = (2/N2).(6.19)
We now obse e by (6.10), (6.19), and (6.6) ha
(D/N2) = (2/N2)(4D2/m) = (2/m)(4D2/m) = (8D2/m)=(D/m).
The p oo is now comple e.
We a e now eady o he p oo s o Theo ems 6.2 and 6.3, whose s a emen s a e
gi en below.
Theo em 6.2. Le U(P, Q)be a nondegene a e LSFK o which gcd(P, Q) = 1 and
D > 0. Le m≥5be an odd p ime o a Lucas pseudop ime o he second kind such
ha gcd(m, PQD) = 1 and 3∤mi P≡Q≡1 (mod 2). Le N1=Um. Suppose
ha N1is composi e i mis an odd p ime. Then N1is a s ong Lucas pseudop ime
i any o he ollowing h ee condi ions a e sa is ied:
(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).
P oo . By Lemma 6.1, N1is a posi i e odd composi e in ege . Since mis odd, i
will hen ollow om Co olla y 3.15 ha N1is a s ong Lucas pseudop ime i we
INTEGERS: 25 (2025) 21
can show ha N1is a Lucas pseudop ime. No ing ha mis an odd p ime o a
Lucas pseudop ime o he second kind, we ind ha
Um≡(D/m) (mod m).(6.20)
We see by (6.20) ha
m|Um−(D/m).(6.21)
I now ollows by P oposi ion 2.3 (iii) and (6.21) ha
N1=Um|UN1−(D/m).
I will hen ollow ha N1is a Lucas pseudop ime i we can show ha
(D/m) = (D/N1).(6.22)
Howe e , (6.22) holds by Lemma 6.1. The p oo is now es ablished.
Theo em 6.2 was p o ed in [22] o he case in which P > 0 and Pis odd.
Theo em 6.3. Le U(P, Q)be a nondegene a e LSFK o which Q=±1. Then
D > 0. Le m≥5be an odd p ime o a Lucas pseudop ime o he second kind
such ha gcd(m, PD) = 1 and 3∤mi P≡1 (mod 2). Le N1=Um. Then
gcd(N1, PD) = 1 and 3∤N1i P≡1 (mod 2). Suppose ha N1is composi e
i mis an odd p ime and Q=−1. Then N1is a s ong Lucas pseudop ime and
a F obenius pseudop ime such ha gcd(N1, PD) = 1 and 3∤N1i P≡Q≡1
(mod 2), i any o he ollowing wo condi ions a e sa is ied:
(i) P≡1 (mod 2);
(ii) P≡0 (mod 2) and Q=−1.
P oo . By Rema k 2.2, D > 0. By Co olla y 4.2 (i) and Theo em 5.1 (i), N1=Umis
composi e. I now ollows om Theo em 6.2 ha N1is a s ong Lucas pseudop ime
i (i) o (ii) holds. We see by Lemma 6.1 ha gcd(N1, PD) = 1. We also see om
Lemma 2.8 ha 3 ∤N1i P≡1 (mod 2). Since Q=±1, i now ollows om
Theo em 3.19 ha N1is also a F obenius pseudop ime i (i) o (ii) holds.
Theo em 6.3 was p o ed in [22] o he case in which P > 0 and Pis odd.
Rema k 6.4. Conside he nondegene a e LSFK U(P, Q), whe e Q=±1. Using
Theo em 6.3, we can explici ly ind in ini ely many F obenius pseudop imes ha
a e also s ong Lucas pseudop imes wi h pa ame e s Pand Q. Le mbe a Lucas
pseudop ime o he second kind such ha gcd(m, PD) = 1 and 3 ∤mi P≡1
(mod 2). Le M1=Umand Mi+1 =UMi o i≥1. Then by Theo em 6.3, Miis a
F obenius pseudop ime o i≥1.

INTEGERS: 25 (2025) 22
Theo em 6.5. Le U(P, Q)be a nondegene a e LSFK o which gcd(P, Q) = 1
and D > 0. Le m≥5be an odd p ime o a F obenius pseudop ime such ha
gcd(m, PQD)=1and 3∤mi P≡Q≡1 (mod 2). Le N2=U2m/P . Then N2is
a Lucas pseudop ime i any o he ollowing h ee condi ions a e sa is ied:
(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).
P oo . By Lemma 6.1, N2is a posi i e odd composi e in ege . Since mis odd, i
ollows om P oposi ion 2.3 ( i) ha P|Vm. By P oposi ion 2.3 (i),
N2=U2m/P =UmVm/P. (6.23)
No ing ha mis an odd p ime o a F obenius pseudop ime such ha gcd(m, D) = 1,
we ind ha
Um≡(D/m) (mod m) and Vm≡P(mod m).(6.24)
The e o e, 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. Consequen ly, by (6.26),
2m|U2m/P −(D/m).(6.27)
The e o e, by P oposi ion 2.3 (iii) and (6.27),
N2=U2m/P |U2m|UN2−(D/m).
To comple e he p oo , we need o show ha
(D/m) = (D/N2).(6.28)
Howe e , (6.28) holds by Lemma 6.1. Theo em 6.5 now ollows.
Theo em 6.5 was p o ed in [22] o he case in which P > 0 and Pis odd.
Theo em 6.6 imp o es on Theo em 6.5 when Q=±1 by showing ha in his
case, U2m(P, Q)/P is a Lucas pseudop ime when mis an odd p ime o a Lucas
pseudop ime a he han equi ing ha mbe an odd p ime o a F obenius pseudo-
p ime. As men ioned abo e in Rema k 3.20, Theo em 6.11 below shows ha he e
a e in ini ely many Lucas pseudop imes ha a e no F obenius pseudop imes.
INTEGERS: 25 (2025) 23
Theo em 6.6. Le U(P, Q)be a nondegene a e LSFK o which Q=±1. Then
D > 0. Le m≥5be an odd p ime o a Lucas pseudop ime such ha gcd(m, P D) =
1and 3∤mi P≡1 (mod 2). Le N2=U2m/P. Then gcd(N2, PD)=1and 3∤N2
i P≡1 (mod 2). Fu he , N2is a Lucas pseudop ime i ei he o he ollowing
wo condi ions is sa is ied:
(i) P≡1 (mod 2);
(ii) P≡0 (mod 2) and Q=−1.
P oo . By Rema k 2.2, D > 0. By Co olla y 4.2 (ii), N2=U2m/P is composi e.
Mo eo e , by Lemma 6.1, N2is a posi i e odd in ege such ha gcd(N2, PD) = 1.
Since mis odd, i ollows om P oposi ion 2.3 ( i) ha P|Vm. By P oposi ion
2.3 (i),
U2m/P =Um(Vm/P).
To comple e he p oo , we need o show ha
UN2−(D/N2)≡0 (mod N2).(6.29)
Le =m−(D/m). Then is e en and by P oposi ion 2.3 (ii),
U2
+1 −U U +2 =Q = 1.(6.30)
Since mis an odd p ime o a Lucas pseudop ime,
U ≡0 (mod m).(6.31)
Thus, by (6.30) and (6.31),
U2
+1 ≡1 (mod m).
Le pbe a p ime such ha pi∥m o some i≥1. Then
U2
+1 ≡1 (mod pi).(6.32)
Since he e exis p imi i e oo s modulo pi, we ha e ha
U +1 ≡ε(mod pi),(6.33)
whe e ε∈(−1,1). Thus, by (6.33) and Lemma 2.5,
V ≡U +1V0≡εV0≡2ε(mod pi), V +1 ≡U +1V1≡εV1≡P ε (mod pi).
(6.34)
The e o e, by (6.30), (6.32), (6.33) and he ecu sion ela ion (1.1) de ining bo h
U(P, Q) and V(P, Q), we ha e ha
−QU −1=U +1 −PU ≡ε−P·0≡ε(mod pi) (6.35)
INTEGERS: 25 (2025) 24
and
−QV −1=V +1 −PV ≡Pε −2Pε ≡ −Pε (mod pi).(6.36)
Since −Q=±1, we see by (6.35) and (6.36) ha
U −1≡ −Qε (mod pi) and V −1≡PQε (mod pi).(6.37)
Now suppose ha (D/m) = 1. Since gcd(P, m) = 1, we see by (6.33), (6.34),
and P oposi ion 2.3 (i) ha
N2=U2m/P =UmVm/P =U +1V +1/P ≡ε(εP )P−1
≡ε2≡1≡(D/m) (mod pi).(6.38)
Nex suppose ha (D/m)=−1. Then by (6.37), (6.38), and P oposi ion 2.3 (i),
N2=U2m/P =UmVm/P =U −1V −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)
whe he (D/m) = 1 o (D/m)=−1 o an a bi a y p ime psuch ha pi∥m.
The e o e, i ollows by (6.40) ha
N2−(D/m)≡0 (mod m).(6.41)
Since N2is odd, we also see ha
N2−(D/m)≡0 (mod 2).(6.42)
No ing ha mis odd, we ind by (6.41) and (6.42) ha
N2−(D/m)≡0 (mod 2m).(6.43)
Since 2m|N2−(D/m) by (6.43), we see by P oposi ion 2.3 (iii) ha
N2=U2m/P |U2m|UN2−(D/m).
I will now ollow by (6.29) ha N2is a Lucas pseudop ime i we can show ha
(D/m) = (D/N2).(6.44)
Howe e , (6.44) holds by Lemma 6.1.
INTEGERS: 25 (2025) 25
Rema k 6.7. Le U(P, Q) be a nondegene a e Lucas sequence wi h disc iminan
D, whe e Q=±1. Suppose u he ha ei he i is he case ha P≡1 (mod 2)
o i is he case ha P≡0 (mod 2) and Q=−1. By Theo em 6.6 and by
Theo em 6.11 below, he e in ac exis in ini ely many Lucas pseudop imes M′
wi h pa ame e s Pand ±1 such ha gcd(M′, PD) = 1, 3 ∤M′i P≡1 (mod 2),
and M′is no a F obenius pseudop ime. Gi en a Lucas pseudop ime M′
1such ha
gcd(M′, PD) = 1 and 3 ∤M′
1i P≡1 (mod 2), we can use Theo em 6.6 o explici ly
ind in ini ely many o he Lucas pseudop imes M′
iwi h pa ame e s Pand Q=±1.
Le M′
i+1 =1
PU2M′
i o i≥1. Then
M′
2, M′
3, M′
4,...,
a e also Lucas pseudop imes Nwi h pa ame e s Pand Q.
Example 6.8. Conside he Fibonacci sequence U(1,−1). We obse e by Tables
1 and 5 o [16] ha he e a e 155 Lucas pseudop imes less han 1 000 000, o which
56 a e also F obenius pseudop imes. The i s 10 Lucas pseudop imes less han
1 000 000 which a e no F obenius pseudop imes a e
323,377,1891,3827,6601,8149,11663,13981,17119,17711.
Theo em 6.9. Conside he LSFK U(P, Q), whe e Q=±1. Le Nbe a Lucas
pseudop ime such ha gcd(N, D)=1and Nis no a s ong Lucas pseudop ime.
Suppose ha 2k∥ρ(N). Then we ha e:
(i) I Q=−1, hen Nis a F obenius pseudop ime i and only i
N≡(D/N) (mod 2k+1)and (D/N) = 1;
(ii) I Q= 1, hen Nis a F obenius pseudop ime i and only i
N≡(D/N) (mod 2k+1).
This is p o ed in Theo em 3.2 o [22].
Theo em 6.10. Conside he nondegene a e LSFK U(P, Q), whe e Q=±1. Then
D > 0. Le m≥5be an odd p ime o a Lucas pseudop ime such ha gcd(m, P D) =
1and 3∤mi Pis odd. Le N2=U2m/P. Suppose ha ei he P≡1 (mod 2) o
i is he case ha P≡0 (mod 2) and Q=−1. Then N2is a Lucas pseudop ime.
Mo eo e , he ollowing hold:
(i) Suppose ha Pis odd and Q=−1. Then N2is a F obenius pseudop ime i
and only i m≡(D/m) (mod 6) and (D/m) = 1.
(ii) Suppose ha Pis odd and Q= 1. Then N2is a F obenius pseudop ime i and
only i m≡(D/m) (mod 6).
(iii) Suppose ha P≡0 (mod 2) and Q=−1. Then N2is a F obenius pseudo-
p ime i and only i m≡(D/m) (mod 4) and (D/m) = 1.
INTEGERS: 25 (2025) 32
[6] P. Hil on, J. Pede sen, L. Some , On Lucasian numbe s, Fibonacci Qua . 35 (1997), 43–47.
[7] P. Kiss, Some esul s on Lucas pseudop imes, Ann. Uni . Sci. Budapes . E˝o ˝os Sec . Ma h.
28 (1985), 153–159.
[8] M. Kˇ ´ıˇzek, L. Some , A. ˇ
Solco ´a, F om g ea disco e ies in numbe heo y o applica ions,
Sp inge , Cham, 2021.
[9] D. H. Lehme , An ex ended heo y o Lucas’ unc ions, Ann. o Ma h. 31 (1930), 419–448.
[10] F. Luca, L. Some , Lucas sequences o which 4 |ϕ(|un|) o almos all n,Fibonacci Qua .
44 (2006), 249–263.
[11] C. Pome ance, J. L. Sel idge, S. S. Wags a , J ., The pseudop imes o 25 ·109,Ma h. Comp.
35 (1980), 1003–1026.
[12] P. Ribenboim, The New Book o P ime Numbe Reco ds, Sp inge , New Yo k, 1996.
[13] A. Ro kiewicz, On Lucas numbe s wi h wo in insic di iso s, Bull. Acad. Polon. Sci. S´e .
Sci. Ma h. As onom. Phys. 10 (1962), 223–232.
[14] A. Ro kiewicz, On he pseudop imes wi h espec o he Lucas sequence, Bull. Acad. Polon.
Sci. S´e . Sci. Ma h. As onom. Phys. 21 (1973), 793–797.
[15] A. Ro kiewicz, Lucas pseudop imes, Func . App ox. Commen . Ma h. 28 (2000), 97–104.
[16] A. Ro kiewicz, Lucas and F obenius pseudop imes, Ann. Ma h. Sil. 17 (2003), 17–39.
[17] A. Schinzel, On p imi i e p ime ac o s o Lehme numbe s I, Ac a A i h. 8(1963), 213–223.
[18] L. Some , Gene aliza ion o a heo em o D obo , Fibonacci Qua . 40 (2002), 435–437.
[19] L. Some , Lucas sequences Uk o which U2pand U2pa e pseudop imes o almos all p imes p,
Fibonacci Qua . 44 (2006), 7–12.
[20] L. Some , M. Kˇ ´ıˇzek, P ime Lehme and Lucas numbe s wi h composi e indices, Fibonacci
Qua . 51 (2013), 194–214.
[21] L. Some , M.Kˇ ´ıˇzek, On p imes in Lucas sequences, Fibonacci Qua . 53 (2015), 2–23.
[22] L. Some , M. Kˇ ´ıˇzek, F obenius, Lucas, and Dickson pseudop imes, Fibonacci Qua . 60
(2022), 325–343.
[23] M. Wa d, P ime di iso s o second o de ecu ing sequences, Duke Ma h. J. 21 (1954),
607–614.
[24] ma hwo ld.wol am.com/FibonacciP ime.h ml