Euler-Jacobi pseudoprime

Definition

Let $n$ be a composite natural number and $a$ be an integer relatively prime to $n$. We say that $n$ is an Euler-Jacobi pseudoprime with respect to the base $a$ if $n$ is odd and:

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$,

where the expression on the right is the Jacobi symbol of $a$ mod $n$. Note that the analogous statement is true for all primes, because for a prime, the Jacobi symbol equals the Legendre symbol.

Relation with other properties

Weaker properties

• Euler pseudoprime
• Fermat pseudoprime

Other related properties

• Strong pseudoprime