Euler pseudoprime

A composite number n is called an Euler pseudoprime to a natural base a if $\scriptstyle a^{\frac {n-1}{2}}\equiv 1{\pmod {n}}$ or $\scriptstyle 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 that satisfies $\scriptstyle a^{\frac {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.

Absolute Euler pseudoprime

An absolute Euler pseudoprime is a composite number c that satisfies the congruence $\scriptstyle a^{\frac {c-1}{2}}\equiv 1{\pmod {c}}$ or $\scriptstyle a^{\frac {n-1}{2}}\equiv \left(-1\right){\pmod {n}}$ for every base a that is coprime to c. Every absolute Euler pseudoprime is also a Carmichael number.

Further reading

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