Editing Euler–Jacobi pseudoprime (section)

== Properties ==

The motivation for this definition is the fact that all [[prime number]]s ''n'' satisfy the above equation, as explained in the [[Euler's criterion]] article. The equation can be tested rather quickly, which can be used for probabilistic [[prime testing|primality testing]]. These tests are over twice as strong as tests based on [[Fermat's little theorem]]. 

Every Euler–Jacobi pseudoprime is also a [[Fermat pseudoprime]] and an [[Euler pseudoprime]]. There are no numbers which are Euler–Jacobi pseudoprimes to all bases as [[Carmichael number]]s are. [[Robert M. Solovay|Solovay]] and [[Volker Strassen|Strassen]] showed that for every composite ''n'', for at least ''n''/2 bases less than ''n'', ''n'' is not an Euler–Jacobi pseudoprime.<ref>{{Cite journal |last=Solovay |first=R. |last2=Strassen |first2=V. |date=1977-03-01 |title=A Fast Monte-Carlo Test for Primality |url=https://epubs.siam.org/doi/10.1137/0206006 |journal=SIAM Journal on Computing |volume=6 |issue=1 |pages=84–85 |doi=10.1137/0206006 |issn=0097-5397}}</ref>

The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·10<sup>9</sup> (see {{oeis|id=A047713}}) (page 1005 of <ref name="PSW">{{cite journal|author2 = [[John L. Selfridge]]|author3= [[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=https://math.dartmouth.edu/~carlp/PDF/paper25.pdf |archive-url=https://web.archive.org/web/20050304202721/http://math.dartmouth.edu/~carlp/PDF/paper25.pdf |archive-date=2005-03-04 |url-status=live|author1 = [[Carl Pomerance]]| doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free}}</ref>).

In the literature (for example,<ref name="PSW"/>), an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.