# Euler pseudoprime

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]
Code [?]

This editable Main Article is under development and subject to a disclaimer.

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

## Properties

${\displaystyle \left(a^{\frac {n-1}{2}}\right)^{2}=a^{n-1}}$
and
${\displaystyle 1^{2}=\left(-1\right)^{2}=1\ }$
• Every Euler Pseudoprime to base a that satisfies ${\displaystyle \scriptstyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$ is an Euler-Jacobi pseudoprime.
• Strong pseudoprimes are Euler pseudoprimes too.

## Absolute Euler pseudoprime

An absolute Euler pseudoprime is a composite number c that satisfies the congruence ${\displaystyle \scriptstyle a^{\frac {c-1}{2}}\equiv 1{\pmod {c}}}$ or ${\displaystyle \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.