Editing Euler–Jacobi pseudoprime

{{Short description|Odd composite number which passes the given congruence}}
In [[number theory]], an [[odd number|odd]] [[integer]] ''n'' is called an '''Euler–Jacobi probable prime''' (or, more commonly, an '''Euler probable prime''') to base ''a'', if ''a'' and ''n'' are [[coprime]], and 

:<math>a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)\pmod{n}</math>

where <math>\left(\frac{a}{n}\right)</math> is the [[Jacobi symbol]].  The Jacobi symbol evaluates to 0 if ''a'' and ''n'' are not coprime, so the test can alternatively be expressed as:

:<math>a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \neq 0 \pmod{n}.</math>

If ''n'' is an odd [[composite number|composite]] integer that satisfies the above congruence, then ''n'' is called an '''Euler–Jacobi pseudoprime''' (or, more commonly, an '''Euler pseudoprime''') to base ''a''.

As long as ''a'' is not a multiple of ''n'' (usually 2 ≤ ''a'' < ''n''), then if ''a'' and ''n'' are not coprime, ''n'' is definitely composite, as 1 < [[Greatest common divisor|gcd]](''a'',''n'') < ''n'' is a factor of ''n''.

== 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.

==Implementation in [[Lua (programming language)|Lua]]==

 '''function''' EulerJacobiTest(k)
         a = 2
         '''if''' k == 1 '''then return false'''
         '''elseif''' k == 2 '''then return true'''
         '''else'''
                 '''if'''([[Modular exponentiation#Implementation in Lua|modPow(a,(k-1)/2,k)]] == [[Jacobi symbol#Implementation in Lua|Jacobi(a,k)]]) '''then'''
                         '''return true'''
                 '''else'''
                         '''return false'''
                 '''end'''
         '''end'''
 '''end'''

==See also==
* [[Probable prime]]

== References ==
{{reflist}}

{{Classes of natural numbers}}
{{DEFAULTSORT:Euler-Jacobi Pseudoprime}}
[[Category:Pseudoprimes]]