# Euler-Jacobi pseudoprime

## Definition

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

,

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