PlanetMath: Solovay-Strassen test

It is known that an odd number

is prime if and only if for every

such that

we have

Proof. It suffices to exhibit one element $a \in \mathbb{Z}_n^*$ which does not satisfy Equation (1). Indeed, if there exists one such element, then the set of all elements which do satisfy Equation (1) forms a proper subgroup of $\mathbb{Z}_n^*$ , from which we conclude that the elements satisfying Equation (1) number no more than half of the elements of $\mathbb{Z}_n^*$ .

We consider separately the cases where is squarefree and not squarefree. If is squarefree, let be a prime dividing and let be a quadratic non-residue mod . Using the Chinese Remainder Theorem, choose an integer $a \in \mathbb{Z}_n^*$ such that:

$\displaystyle a$	$\displaystyle \equiv b \pmod{p},$
$\displaystyle a$	$\displaystyle \equiv 1 \pmod{\frac{n}{p}}.$

The Jacobi symbol ${\genfrac{(}{)}{}{}{a}{n}}$ is given by

$\displaystyle {\genfrac{(}{)}{}{}{a}{n}} = {\genfrac{(}{)}{}{}{a}{p}} {\genfrac... ...= {\genfrac{(}{)}{}{}{b}{p}} {\genfrac{(}{)}{}{}{1}{n/p}} = (-1) \cdot 1 = -1.$

We will assume that $a^{\frac{n-1}{2}} \equiv -1 \pmod{n}$ and derive a contradiction. The equation $a^{\frac{n-1}{2}} \equiv -1 \pmod{n}$ implies that $a^{\frac{n-1}{2}} \equiv -1 \pmod{\frac{n}{p}}$ . However, since $a \equiv 1 \pmod{\frac{n}{p}}$ , we must have $a^{\frac{n-1}{2}} \equiv 1 \pmod{\frac{n}{p}}$ , so that $1 \equiv -1 \pmod{\frac{n}{p}}$ , which is a contradiction.

Now suppose that is not squarefree. Let be a prime such that $p^2 \div n$ , and set $a = 1 + \frac{n}{p}$ . By the binomial theorem, we have

$\displaystyle a^p = \left(1+\frac{n}{p}\right)^p = 1 + \binom{p}{1}\left(n/p\ri... ...left(n/p\right)^2 + \cdots + \binom{p}{p}\left(n/p\right)^p \equiv 1 \pmod{n},$

so the multiplicative order of $a \bmod n$ is equal to

, and hence in particular $a^{n-1} \neq 1 \pmod{n}$ , since $p \nmid n-1$ . On the other hand,

$\displaystyle {\genfrac{(}{)}{}{}{a}{n}} = {\genfrac{(}{)}{}{}{1+\frac{n}{p}}{n... ...ac{n}{p}}{n/p}} = {\genfrac{(}{)}{}{}{1}{p}} {\genfrac{(}{)}{}{}{1}{n/p}} = 1,$

does not satisfy Equation (1). $\qedsymbol$