Editing Lucas pseudoprime

{{Short description|Probabilistic test for the primality of an integer}}
'''Lucas pseudoprimes''' and '''Fibonacci pseudoprimes'''  are [[composite number|composite]] integers that pass certain tests which all [[Prime number|prime]]s and very few composite numbers pass: in this case, criteria relative to some [[Lucas sequence]].

== Baillie-Wagstaff-Lucas pseudoprimes ==

Baillie and Wagstaff define Lucas pseudoprimes as follows:<ref name="lpsp">{{cite journal |author1 = Robert Baillie |author2 = Samuel S. Wagstaff, Jr. |author-link2 = Samuel S. Wagstaff, Jr. |title=Lucas Pseudoprimes |journal=Mathematics of Computation |date=October 1980 |volume=35 |issue=152 |pages=1391–1417 |url=http://mpqs.free.fr/LucasPseudoprimes.pdf |mr=583518 |jstor=2006406 |doi=10.1090/S0025-5718-1980-0583518-6 |doi-access=free }}</ref> Given integers ''P'' and ''Q'', where ''P'' > 0 and <math>D=P^2-4Q</math>,
let ''U<sub>k</sub>''(''P'', ''Q'') and ''V<sub>k</sub>''(''P'', ''Q'') be the corresponding [[Lucas sequence]]s.

Let ''n'' be a positive integer and let <math>\left(\tfrac{D}{n}\right)</math> be the [[Jacobi symbol]]. We define

: <math>\delta(n)=n-\left(\tfrac{D}{n}\right).</math>

If ''n'' is a [[prime number|prime]] that does not divide ''Q'', then the following congruence condition holds:

{{NumBlk|:|<math>U_{\delta(n)} \equiv 0 \pmod {n}.</math>|{{EquationRef|1}}}}

If this congruence does ''not'' hold, then ''n'' is ''not'' prime.
If ''n'' is ''composite'', then this congruence ''usually'' does not hold.<ref name="lpsp"/> These are the key facts that make Lucas sequences useful in [[primality test]]ing.

The congruence ({{EquationNote|1}}) represents one of two congruences defining a [[Frobenius pseudoprime]]. Hence, every Frobenius pseudoprime is also a Baillie-Wagstaff-Lucas pseudoprime, but the converse does not always hold.

Some good references are chapter 8 of the book by Bressoud and Wagon (with [[Mathematica]] code),<ref name="Bressoud">
{{cite book | author = David Bressoud | author-link = David Bressoud | author2 = Stan Wagon | author-link2 = Stan Wagon | title = A Course in Computational Number Theory | publisher = Key College Publishing in cooperation with Springer | location = New York | year = 2000 | isbn = 978-1-930190-10-8 | url-access = registration | url = https://archive.org/details/courseincomputat0000bres }}
</ref> pages 142–152 of the book by Crandall and Pomerance,<ref name="CrandallPomerance">
{{cite book | title=Prime numbers: A computational perspective | edition=2nd | author=Richard E. Crandall | author-link=Richard Crandall |author2=Carl Pomerance |author-link2=Carl Pomerance | publisher=[[Springer-Verlag]] | year=2005 | isbn=0-387-25282-7}}
</ref> and pages 53–74 of the book by Ribenboim.<ref name="Ribenboim">
{{cite book | title=The New Book of Prime Number Records | author=Paulo Ribenboim |author-link=Paulo Ribenboim | publisher=[[Springer-Verlag]] | year=1996 | isbn=0-387-94457-5 }}
</ref>

==Lucas probable primes and pseudoprimes==

A '''Lucas probable prime''' for a given (''P, Q'') pair is ''any'' positive integer ''n'' for which equation ({{EquationNote|1}}) above is true (see,<ref name="lpsp"/> page 1398).

A '''Lucas pseudoprime''' for a given (''P, Q'') pair is a positive ''composite'' integer ''n'' for which equation ({{EquationNote|1}}) is true (see,<ref name="lpsp"/> page 1391).

A Lucas probable prime test is most useful if ''D'' is chosen such that the Jacobi symbol <math>\left(\tfrac{D}{n}\right)</math> is &minus;1
(see pages 1401–1409 of,<ref name="lpsp"/> page 1024 of,<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref> or pages 266–269 of <ref name="Bressoud"/>
).  This is especially important when combining a Lucas test with a [[strong pseudoprime]] test, such as the [[Baillie–PSW primality test]].  Typically implementations will use a parameter selection method that ensures this condition (e.g. the Selfridge method recommended in <ref name="lpsp"/> and described below).

If <math>\left(\tfrac{D}{n}\right)=-1,</math> then equation ({{EquationNote|1}}) becomes
{{NumBlk|:|<math>U_{n+1} \equiv 0 \pmod {n}.</math>|{{EquationRef|2}}}}

If congruence ({{EquationNote|2}}) is false, this constitutes a proof that ''n'' is composite.

If congruence ({{EquationNote|2}}) is true, then ''n'' is a Lucas probable prime.
In this case, either ''n'' is prime or it is a Lucas pseudoprime.
If congruence ({{EquationNote|2}}) is true, then ''n'' is ''likely'' to be prime (this justifies the term '''probable''' prime), but this does not ''prove'' that ''n'' is prime.
As is the case with any other probabilistic primality test, if we perform additional Lucas tests with different ''D'', ''P'' and ''Q'', then unless one of the tests proves that ''n'' is composite, we gain more confidence that ''n'' is prime.

Examples: If ''P'' = 3, ''Q'' = &minus;1, and ''D'' = 13, the sequence of ''U'''s is {{oeis|id=A006190}}: ''U<sub>0</sub>'' = 0, ''U<sub>1</sub>'' = 1, ''U<sub>2</sub>'' = 3, ''U<sub>3</sub>'' = 10, etc.

First, let ''n'' = 19. The Jacobi symbol <math>\left(\tfrac{13}{19}\right)</math> is &minus;1, so  δ(''n'') = 20, ''U<sub>20</sub>'' = 6616217487 = 19·348221973 and we have
:<math> U_{20} = 6616217487 \equiv 0 \pmod {19} . </math>
Therefore, 19 is a Lucas probable prime for this (''P, Q'') pair. In this case 19 is prime, so it is ''not'' a Lucas pseudoprime.

For the next example, let ''n'' = 119. We have <math>\left(\tfrac{13}{119}\right)</math> = &minus;1, and we can compute
:<math> U_{120} \equiv 0 \pmod {119}. </math>
However, 119 = 7·17 is not prime, so 119 is a Lucas ''pseudoprime'' for this (''P, Q'') pair.
In fact, 119 is the smallest pseudoprime for ''P'' = 3, ''Q'' = &minus;1.

We will see [[Lucas pseudoprime#Implementing a Lucas probable prime test|below]] that, in order to check equation ({{EquationNote|2}}) for a given ''n'', we do ''not'' need to compute all of the first ''n'' + 1 terms in the ''U'' sequence.

Let ''Q'' = −1, the smallest Lucas pseudoprime to ''P'' = 1, 2, 3, ... are
:323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...

==Strong Lucas pseudoprimes==
Now, factor <math>\delta(n)=n-\left(\tfrac{D}{n}\right)</math> into the form <math>d\cdot2^s</math> where <math>d</math> is odd.

A '''strong Lucas pseudoprime''' for a given (''P'', ''Q'') pair is an odd composite number ''n'' with GCD(''n, D'') = 1, satisfying one of the conditions

:<math>  U_d \equiv 0 \pmod n  </math>
or
:<math>  V_{d \cdot 2^r} \equiv 0 \pmod n  </math>

for some 0 &le; ''r'' &lt; ''s''; see page 1396 of.<ref name="lpsp"/> A strong Lucas pseudoprime is also a Lucas pseudoprime (for the same (''P'', ''Q'') pair), but the converse is not necessarily true.
Therefore, the '''strong''' test is a more stringent primality test than equation ({{EquationNote|1}}).

There are infinitely many strong Lucas pseudoprimes, and therefore, infinitely many Lucas pseudoprimes.
Theorem 7 in <ref name="lpsp"/> states: Let <math>P</math> and <math>Q</math> be relatively prime positive integers for which <math>P^2 - 4Q</math> is positive but not a square. Then there is a positive constant <math>c</math> (depending on <math>P</math> and <math>Q</math>) such that the number of strong Lucas pseudoprimes not exceeding <math>x</math> is greater than <math>c \cdot \log x</math>, for <math>x</math> sufficiently large.

We can set ''Q'' = −1, then <math>U_n</math> and <math>V_n</math> are ''P''-Fibonacci sequence and ''P''-Lucas sequence, the pseudoprimes can be called '''strong Lucas pseudoprime in base ''P''''', for example, the least strong Lucas pseudoprime with ''P'' = 1, 2, 3, ... are 4181, 169, 119, ...

An '''extra strong Lucas pseudoprime'''<ref name=ExtraStrong>{{cite tech report
 |first1=Zheiyu |last1=Mo  |first2=James P. |last2=Jones
 |title=A new primality test using Lucas sequences
 |type=preprint
}} cited in {{cite journal
 |title=A Probable Prime Test With High Confidence
 |first=Jon |last=Grantham
 |journal=Journal of Number Theory
 |year=1998 |volume=72 |issue=1 |pages=32–47 |article-number=NT982247
 |doi=10.1006/jnth.1998.2247
 |arxiv=1903.06823 |citeseerx=10.1.1.56.8827 |s2cid=119640473 
 |url=https://les-mathematiques.net/vanilla/uploads/editor/ix/sp1k717k3k9a.pdf <!-- |url=http://www.pseudoprime.com/pseudo2.ps-->
}}</ref><ref name="FrobeniusPSP">{{cite journal
 |title=Frobenius Pseudoprimes
 |first=Jon |last=Grantham
 |journal=Mathematics of Computation |year=2001 |volume=70 |issue=234 |pages=873–891
 |doi=10.1090/S0025-5718-00-01197-2 |doi-access=free
 |arxiv=1903.06820 |mr=1680879 |bibcode=2001MaCom..70..873G
 |url=http://www.pseudoprime.com/pseudo1.ps
}}</ref>
is a strong Lucas pseudoprime for a set of parameters (''P'', ''Q'') where ''Q'' = 1, satisfying one of the conditions

:<math>  U_d \equiv 0  \text{  and  } V_d \equiv \pm 2 \pmod {n}  </math>
or
:<math>  V_{d \cdot 2^r} \equiv 0 \pmod {n}  </math>

for some <math> 0 \le r < s-1</math>. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same <math>(P,Q)</math> pair.  No number can be a strong Lucas pseudoprime to more than {{frac|4}} of all bases, or an extra strong Lucas pseudoprime to more than {{frac|8}} of all bases.

==Implementing a Lucas probable prime test==
Before embarking on a probable prime test, one usually verifies that ''n'', the number to be tested for primality, is odd, is not a perfect square, and is not divisible by any small prime less than some convenient limit. Perfect squares are easy to detect using [[Newton's method]] for square roots.

We choose a Lucas sequence where the Jacobi symbol <math>\left(\tfrac{D}{n}\right)=-1</math>, so that δ(''n'') = ''n'' + 1.

Given ''n'', one technique for choosing ''D'' is to use trial and error to find the first ''D'' in the sequence 5, −7, 9, −11, ... such that <math>\left(\tfrac{D}{n}\right)=-1</math>. Note that <math>\left(\tfrac{k}{n}\right)\left(\tfrac{-k}{n}\right)=-1</math>.
(If ''D'' and ''n'' have a prime factor in common, then <math>\left(\tfrac{D}{n}\right)=0.</math>).
With this sequence of ''D'' values, the average number of ''D'' values that must be tried before we encounter one whose Jacobi symbol is &minus;1 is about 1.79.{{r|lpsp|p=1416}}
Once we have ''D'', we set <math>P=1</math> and <math>Q=(1-D)/4</math>.
It is a good idea to check that ''n'' has no prime factors in common with ''P'' or ''Q''.
This method of choosing ''D'', ''P'', and ''Q'' was suggested by [[John Selfridge]].

(This search will never succeed if ''n'' is square, and conversely if it does succeed, that is proof that ''n'' is not square.  Thus, some time can be saved by delaying testing ''n'' for squareness until after the first few search steps have all failed.)

Given ''D'', ''P'', and ''Q'', there are recurrence relations that enable us to quickly compute <math>U_{n+1}</math> and <math>V_{n+1}</math> in <math>O(\log_2 n)</math> steps; see {{slink|Lucas sequence|Other relations}}. To start off, 
:<math>U_1=1</math>
:<math>V_1=P</math>
:<math>Q^1=Q</math>

First, we can double the subscript from <math>k</math> to <math>2k</math> in one step using the recurrence relations
:<math>U_{2k}=U_k\cdot V_k,</math>
:<math>V_{2k}=V_k^2-2Q^k=\frac{V_k^2+DU_k^2}{2},</math>
:<math>Q^{2k}=(Q^k)^2.</math>
Next, we can increase the subscript by 1 using the recurrences
:<math>U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2,</math>
:<math>V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2,</math>
:<math>Q^{2k+1}=Q\cdot Q^{2k}.</math>
At each stage, we reduce all of the variables modulo ''n''.  When dividing by 2 [[modular arithmetic|modulo]] ''n'', if the numerator is odd add ''n'' (which does not change the value modulo ''n'') to make it even before dividing by 2.'

We use the bits of the binary expansion of ''n'' to determine ''which'' terms in the sequence to compute. For example, if ''n''+1 = 44 (= 101100 in binary), then, taking the bits one at a time from left to right, we obtain the sequence of indices to compute: 1<sub>2</sub> = 1, 10<sub>2</sub> = 2, 100<sub>2</sub> = 4, 101<sub>2</sub> = 5, 1010<sub>2</sub> = 10, 1011<sub>2</sub> = 11, 10110<sub>2</sub> = 22, 101100<sub>2</sub> = 44. Therefore, we compute ''U''<sub>1</sub>, ''U''<sub>2</sub>, ''U''<sub>4</sub>, ''U''<sub>5</sub>, ''U''<sub>10</sub>, ''U''<sub>11</sub>, ''U''<sub>22</sub>, and ''U''<sub>44</sub>. We also compute the same-numbered terms in the ''V'' sequence, along with ''Q''<sup>1</sup>, ''Q''<sup>2</sup>, ''Q''<sup>4</sup>, ''Q''<sup>5</sup>, ''Q''<sup>10</sup>, ''Q''<sup>11</sup>, ''Q''<sup>22</sup>, and ''Q''<sup>44</sup>.

By the end of the calculation, we will have computed ''U<sub>n+1</sub>'', ''V<sub>n+1</sub>'', and ''Q<sup>n+1</sup>'', (mod ''n'').
We then check congruence ({{EquationNote|2}}) using our expected value of ''U<sub>n+1</sub>''.

When the parameters ''D'', ''P'', and ''Q'' are chosen as described above, the first 10 Lucas pseudoprimes are:{{r|lpsp|p=1401}}
323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 {{OEIS|id=A217120}}

The '''strong''' versions of the Lucas test can be implemented in a similar way.  With the same parameters, the first 10 ''strong'' Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519
{{OEIS|id=A217255}}

''Extra strong'' Lucas pseudoprimes use different parameters: fix <math>Q = 1</math>.
Then try ''P'' = 3, 4, 5, 6, ..., until a value of <math>D=P^2-4Q</math> is found so that the Jacobi symbol <math>\left(\tfrac{D}{n}\right)=-1</math>.  The first 10 ''extra strong'' Lucas pseudoprimes are
989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389
{{OEIS|id=A217719}}

===Checking additional congruence conditions===
If we have checked that congruence ({{EquationNote|2}}) is true, there are additional congruence conditions we can check that have almost no additional computational cost.  By providing an additional opportunity for ''n'' to be proved composite, these increase the reliability of the test.

If ''n'' is an odd prime and <math>\left(\tfrac{D}{n}\right)=-1</math>, then we have the following:{{r|lpsp|p=1392 Eq. 2}}

{{NumBlk|:|<math>V_{n+1} \equiv 2 Q \pmod n.</math>|{{EquationRef|3}}}}

Although this congruence condition is not part of the Lucas probable prime test proper, it is almost free to check this condition because, as noted above, the easiest way to compute ''U''<sub>''n''+1</sub> is to compute ''V''<sub>''n''+1</sub> as well.

If  Selfridge's method (above) for choosing parameters is modified so that, if it selects ''D'' = 5, it uses the parameters ''P'' = ''Q'' = 5 rather than ''P'' = 1, ''Q'' = −1, then 913 = 11·83 is the ''only'' composite less than 10<sup>8</sup> for which congruence ({{EquationNote|3}}) is true (see page 1409 and Table 6 of;<ref name="lpsp"/>). More extensive calculations show that, with this method of choosing ''D'', ''P'', and ''Q'', there are only five odd, composite numbers less than 10<sup>15</sup> for which congruence ({{EquationNote|3}}) is true.<ref name=bpsw2>{{cite journal |first1=Robert |last1=Baillie |first2=Andrew |last2=Fiori |first3=Samuel S. Jr. |last3=Wagstaff |author-link3=Samuel S. Wagstaff, Jr. |title=Strengthening the Baillie-PSW Primality Test |journal=Mathematics of Computation |date=July 2021 |volume=90 |issue=330 |pages=1931–1955 |doi=10.1090/mcom/3616 |arxiv=2006.14425 |s2cid=220055722 }}</ref>

If <math>Q \neq \pm 1 </math> (and GCD(''n'', ''Q'') = 1), then an [[Euler–Jacobi probable prime]] test to the base Q can also be implemented at minor computational cost.

The computation of <math>V_{n+1}</math> depends on <math>V_{(n+1)/2}</math> and <math>Q^{(n+1)/2}</math>.  This is <math>Q</math> times <math>Q^{(n-1)/2}</math>, and if ''n'' is prime, then by [[Euler's criterion]],
:<math>  Q^{(n-1)/2} \equiv \left(\tfrac{Q}{n}\right) \pmod {n}  </math> .
(Here, <math>\left(\tfrac{Q}{n}\right)</math> is the [[Legendre symbol]]; if ''n'' is prime, this is the same as the Jacobi symbol).

Therefore, if ''n'' is prime, we must have,
{{NumBlk|:|<math>Q^{(n+1)/2} \equiv Q \cdot Q^{(n-1)/2} \equiv Q \cdot \left(\tfrac{Q}{n}\right) \pmod n.</math>|{{EquationRef|4}}}}

The Jacobi symbol on the right side is easy to compute, so this congruence is easy to check.
If this congruence does not hold, then ''n'' cannot be prime. Provided GCD(''n, Q'') = 1 then testing for congruence ({{EquationNote|4}}) is equivalent to augmenting our Lucas test with a "base Q" [[Solovay–Strassen primality test]].

There is one more<!--There are two conditions, equations (3) and (4) from the paper, but if the V_{n+1} condition (2) is true, then they are equivalent.--> congruence condition on <math>U_n</math> and <math>V_n</math> which must be true if ''n'' is prime and can be checked.{{r|lpsp|p=§2,6}}

== Comparison with the Miller–Rabin primality test ==

''k'' applications of the [[Miller–Rabin primality test]] declare a composite ''n'' to be probably prime with a probability at most (1/4)<sup>''k''</sup>.

There is a similar probability estimate for the strong Lucas probable prime test.<ref>{{cite journal|title=The Rabin-Monier Theorem for Lucas Pseudoprimes|journal=Mathematics of Computation|date=April 1997|volume=66|issue=218|pages=869–881|author=F. Arnault|doi=10.1090/s0025-5718-97-00836-3|citeseerx=10.1.1.192.4789}}</ref>

Aside from two trivial exceptions (see below), the fraction of (''P'',''Q'') pairs (modulo ''n'') that declare a composite ''n'' to be probably prime is at most (4/15).

Therefore, ''k'' applications of the strong Lucas test would declare a composite ''n'' to be probably prime with a probability at most (4/15)<sup>k</sup>.

There are two trivial exceptions. One is ''n'' = 9. The other is when ''n'' = ''p''(''p''+2) is the product of two [[twin prime]]s. Such an ''n'' is easy to factor, because in this case, ''n''+1 = (''p''+1)<sup>2</sup> is a perfect square. One can quickly detect perfect squares using [[Newton's method]] for square roots.

By combining a Lucas pseudoprime test with a [[Fermat primality test]], say, to base 2, one can obtain very powerful probabilistic tests for primality, such as the [[Baillie–PSW primality test]].

==Fibonacci pseudoprimes==
When ''P'' = 1 and ''Q'' = &minus;1, the ''U<sub>n</sub>''(''P'',''Q'') sequence represents the Fibonacci numbers.

A '''Fibonacci pseudoprime''' is often<ref name="Bressoud"/>{{rp|264,}}<ref name="CrandallPomerance"/>{{rp|142,}}<ref name="Ribenboim"/>{{rp|127}}
defined as a composite number ''n'' not divisible by 5 for which congruence ({{EquationNote|1}}) holds with ''P'' = 1 and ''Q'' = &minus;1. By this definition, the Fibonacci pseudoprimes form a sequence:
: 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... {{OEIS|id=A081264}}.  
The references of Anderson and Jacobsen below use this definition.

If ''n'' is congruent to 2 or 3 modulo 5, then Bressoud,<ref name="Bressoud"/>{{rp|272–273}} and Crandall and Pomerance<ref name="CrandallPomerance"/>{{rp|143,168}} point out that it is rare for a Fibonacci pseudoprime to also be a [[Fermat pseudoprime]] base 2.  However, when ''n'' is congruent to 1 or 4 modulo 5, the opposite is true, with over 12% of Fibonacci pseudoprimes under 10<sup>11</sup> also being base-2 Fermat pseudoprimes.

If ''n'' is prime and GCD(''n'', ''Q'') = 1, then we also have<ref name="lpsp"/>{{rp|1392}}
{{NumBlk|:|<math>V_n(P,Q) \equiv P \pmod{n}.</math>|{{EquationRef|5}}}}

This leads to an alternative definition of Fibonacci pseudoprime:<ref name = FibonacciPSP>{{cite journal |author1 = Adina Di Porto |author2 = Piero Filipponi |title = More on the Fibonacci Pseudoprimes |journal = Fibonacci Quarterly |date = 1989 |volume = 27 |issue = 3 |pages = 232–242 |url = https://www.fq.math.ca/Issues/27-3.pdf}}</ref><ref>{{cite journal |author=Di Porto, Adina |author2=Filipponi, Piero |author3=Montolivo, Emilio |title=On the generalized Fibonacci pseudoprimes |journal=Fibonacci Quarterly |volume=28 |pages=347–354 |date=1990 |citeseerx=10.1.1.388.4993}}</ref>
: a '''Fibonacci pseudoprime''' is a composite number ''n'' for which congruence ({{EquationNote|5}}) holds with ''P'' = 1 and ''Q'' = &minus;1.
This definition leads the Fibonacci pseudoprimes form a sequence:
: 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... {{OEIS|id=A005845}},
which are also referred to as ''Bruckman-Lucas'' pseudoprimes.<ref name="Ribenboim"/>{{rp|129}}
Hoggatt and Bicknell studied properties of these pseudoprimes in 1974.<ref>{{cite journal |author1 = V. E. Hoggatt, Jr. |author-link1 = Verner Emil Hoggatt Jr. |author2 = Marjorie Bicknell |title = Some Congruences of the Fibonacci Numbers Modulo a Prime p |journal = Mathematics Magazine |date = September 1974 |volume = 47 |issue = 4 |pages = 210–214 |doi = 10.2307/2689212 |jstor = 2689212}}</ref> Singmaster computed these pseudoprimes up to 100000.<ref>{{cite journal |author = David Singmaster |title=Some Lucas Pseudoprimes |journal=Abstracts Amer. Math. Soc. |date=1983 |volume=4 |issue=83T–10–146 |page=197}}</ref> Jacobsen lists all 111443 of these pseudoprimes less than 10<sup>13</sup>.<ref>{{cite web |title = Pseudoprime Statistics and Tables |url = http://ntheory.org/pseudoprimes.html |access-date = 5 May 2019}}</ref>

It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5).<ref name = Bruckman>{{cite journal |author = P. S. Bruckman |title = Lucas Pseudoprimes are odd |journal = Fibonacci Quarterly |date = 1994 |volume = 32 |pages = 155–157}}</ref><ref>{{cite journal|author=Di Porto, Adina|title=Nonexistence of Even Fibonacci Pseudoprimes of the First Kind|journal=Fibonacci Quarterly|volume=31|pages=173–177|date=1993|citeseerx=10.1.1.376.2601}}</ref> However, even Fibonacci pseudoprimes do exist {{OEIS|id=A141137}} under the first definition given by ({{EquationNote|1}}).

A '''strong Fibonacci pseudoprime''' is a composite number ''n'' for which congruence ({{EquationNote|5}}) holds for ''Q'' = &minus;1 and all ''P''.<ref name="Muller">{{cite conference|author=Müller, Winfried B.|author2=Oswald, Alan|title=Generalized Fibonacci Pseudoprimes and Probable Primes|editor=G.E. Bergum|book-title=Applications of Fibonacci Numbers|volume=5|pages=459–464|publisher=Kluwer|date=1993|doi=10.1007/978-94-011-2058-6_45|display-editors=etal}}</ref>  It follows<ref name="Muller"/>{{rp|460}} that an odd composite integer ''n'' is a strong Fibonacci pseudoprime if and only if:
#''n'' is a [[Carmichael number]]
#2(''p'' + 1) | (''n'' &minus; 1) or 2(''p'' + 1) | (''n'' &minus; ''p'') for every prime ''p'' dividing ''n''.

The smallest example of a strong Fibonacci pseudoprime is 443372888629441 = 17·31·41·43·89·97·167·331.

==Pell pseudoprimes==
A '''Pell pseudoprime''' may be defined as a composite number ''n'' for which equation ({{EquationNote|1}}) above is true with ''P'' = 2 and ''Q'' = &minus;1; the sequence ''U<sub>n</sub>'' then being the [[Pell sequence]].  The first pseudoprimes are then 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

This differs from the definition in {{OEIS2C|id=A099011}} which may be written as:

: <math> \text{  } U_n \equiv \left(\tfrac{2}{n}\right) \pmod {n}</math>

with (''P'', ''Q'') = (2, −1) again defining ''U<sub>n</sub>'' as the [[Pell sequence]].  The first pseudoprimes are then 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215 ...

A third definition uses equation (5) with (''P'', ''Q'') = (2, −1), leading to the pseudoprimes 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...

==References==
{{reflist}}

==External links==
* Anderson, Peter G. [http://www.cs.rit.edu/usr/local/pub/pga/fpp_and_entry_pts Fibonacci Pseudoprimes, their factors, and their entry points.]
* Anderson, Peter G. [http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp Fibonacci Pseudoprimes under 2,217,967,487 and their factors.]
* Jacobsen, Dana [http://ntheory.org/pseudoprimes.html Pseudoprime Statistics, Tables, and Data] (data for Lucas, Strong Lucas, AES Lucas, ES Lucas pseudoprimes below 10<sup>14</sup>; Fibonacci and Pell pseudoprimes below 10<sup>12</sup>)
* {{MathWorld|urlname=FibonacciPseudoprime|title=Fibonacci Pseudoprime}}
* {{MathWorld|urlname=LucasPseudoprime|title=Lucas Pseudoprime}}
* {{MathWorld|urlname=StrongLucasPseudoprime|title=Strong Lucas Pseudoprime}}
* {{MathWorld|urlname=ExtraStrongLucasPseudoprime|title=Extra Strong Lucas Pseudoprime}}

{{Classes of natural numbers}}

[[Category:Fibonacci numbers]]
[[Category:Pseudoprimes]]