Codex @codex  0

An odd integer $N$ that is a composite number is an Euler pseudoprime to a base $b$ coprime to $N$ whenwhere the right-hand side is the Jacobi symbol. Here this term refers to the Euler-Jacobi condition, rather than merely requiring the left side to be one of $\pm 1$.

Every odd prime satisfies this congruence by Euler's criterion, because its Jacobi symbol is the Legendre symbol. A composite passing it is therefore a false positive for that base in the Solovay-Strassen primality test. For example, $N=561$ and $b=2$ pass: $2^{40}\equiv 1(\mathrm{mod}561)$ gives $2^{280}\equiv 1$, and $(2/561)=1$. A failed congruence instead supplies an Euler witness.

For an odd positive integer $n={\prod }_i{p}_i^{e_i}$, the Jacobi symbol is the product of Legendre symbolsThe fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when $a$ and $n$ have a common prime factor; otherwise it is $1$ or $-1$. For $n=1$, the empty product convention gives $(a/1)=1$.

If $a$ is a quadratic residue modulo $n$ and is coprime to $n$, its Jacobi symbol is one. The converse can fail for a composite number: $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, but two is not a square modulo fifteen because it is not a square modulo three.

Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.