The law of quadratic reciprocity, noticed by Euler and Legendre and proved by Gauss, helps greatly in the computation of the Legendre symbol.

Theorem: Let $p,q$ be distinct odd primes. If $p=q=-1(mod4)$, then

otherwise

which we can state as

Proof: From the last theorem on the previous page, we need only show

where $m=\lfloor q/p\rfloor +\lfloor 2q/p\rfloor +...+\lfloor ((p-1)/2)q/p\rfloor$, and $n$ is similarly defined by swapping $p$ and $q$.

Eisenstein found an elegant geometrical proof. Consider the line $L$ from $(\mathrm{0,0})$ to $(p,q)$, and the rectangle $R$ with corners at $(\mathrm{0,0})$ and $(p/2,q/2)$. How many lattice points lie strictly in $R$?

Simply computing the area of a rectangle gives $(p-1)(q-1)/4$. Alternatively, we can count the number of points above and below $L$ inside $R$, since no lattice points can lie on $L$ in $R$ since $p,q$ are coprime.

Consider the points below $L$ on the line $x=1$. They have $y$-coordinates of $1,2,...,\lfloor q/p\rfloor$. When $x=2$, there are $\lfloor 2q/p\rfloor$ points, and so on, giving a total of $m$ points below the $L$. Similarly there are $n$ points above $L$ in $R$, proving the result.

We can restate the proof algebraically. Consider the numbers $py-qx$ for $x=1,...,(p-1)/2$ and $y=1,...,(q-1)/2$. There are a total of $(p-1)(q-1)/4$ numbers, not necessarily distinct. None are zero, since $p,q$ are coprime. The result follows after observing that $n$ of them are positive, and $m$ are negative.

Example:

since $2=-5(mod8)$. Next,

Hence $31$ is a quadratic nonresidue modulo $103$.

Note we had to factor a number during this computation, so for large numbers this method is not efficient without a fast factoring algorithm. Of course, to compute the Legendre symbol, we can simply perform a modular exponentiation, but it turns out by extending the Legendre symbol we can salvage the above method.

The Jacobi symbol $\left(\frac{a}{b}\right)$ is defined for all odd positive integers $b$ and all integers $a$. When $b$ is prime, it is equivalent to the Legendre symbol (which is why we reuse the notation). If $b=1$, define $\left(\frac{a}{1}\right)=1$. Lastly, for other values of $b$, factor $b$ into primes: $b=p_1^{k_1}...p_n^{k_n}$ and define

Thus for odd positive integers $b,b_1,b_2$ we have

Other properties of the Legendre symbol carry over. By inducting on the number of primes in the factorization of $b$, one can show:

The last property allows us to compute the Jacobi symbol without factoring.

Example:

Hence $31$ is a quadratic nonresidue modulo $103$.