Jacobi Symbol - Primality Testing

Primality Testing

There is another way the Jacobi and Legendre symbols differ. If the Euler criterion formula is used modulo a composite number, the result may or may not be the value of the Jacobi symbol.

So if it's not known whether a number n is prime or composite, we can pick a random number a, calculate the Jacobi symbol and compare it with Euler's formula; if they differ modulo n, then n is composite; if they're the same modulo n for many different values of a, then n is "probably prime".

This is the basis for the probabilistic Solovay–Strassen primality test and its refinement the Miller–Rabin primality test.