Euler pseudoprime

A composite number n is called an Euler pseudoprime to a natural base a, if $a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}$ or $a^{\frac {n-1}{2}}\equiv \left(-1\right){\pmod {n}}$

Properties

• Every Euler pseudoprime is odd.
• Every Euler pseudoprime is also a Fermat pseudoprime:

$\left(a^{\frac {n-1}{2}}\right)^{2}=a^{n-1}$

and

$1^{2}=\left(-1\right)^{2}=1\$

• Every Euler Pseudoprime to base a, which satisfy $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ is an Euler-Jacobi pseudoprime.
• Carmichael numbers and Strong pseudoprimes are Euler pseudoprimes too.

Further reading

• Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag, ISBN 0-387-25282-7
• Paolo Ribenboim: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5