Editing Euler–Jacobi pseudoprime (section)

{{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''.