Let p be an odd prime number.
If the equationx² = n mod phas a solution then n is a square mod p, or in classical terminology, n is a quadratic residue mod p.
Half of the numbers between 0 and p are quadratic residues and half are not.
The residues are distributed somewhat randomly.
For large p, quadratic residues are distributed enough like random numbers to be useful in cryptographic applications.
For example, see this post.
But the distribution isn’t entirely random as we’ll demonstrate here.
First let’s look at a couple illustrations, using p = 101 and p = 103.
We’ll use the following Python code to plot the residues.
import matplotlib.
pyplot as plt for p in [101, 103]: s = {x**2 % p for x in range(1, p)} for q in s: plt.
vlines(q, 0, 1) plt.
title(“Quadratic residues mod {}”.
format(p)) plt.
savefig(“residues_mod_{}.
svg”.
format(p)) plt.
close() Here are the plots.
Symmetry and anti-symmetryIf you look closely at the first image, you’ll notice it appears to be symmetric about the middle.
And if you look closely at the second image, you’ll notice it appears to be anti-symmetric, i.
e.
the left side has bars where the right side has gaps and vice versa.
The following code shows that these observations are correct.
p = 101 s = {x**2 % p for x in range(1, p)} for q in s: assert(p – q in s) p = 103 s = {x**2 % p for x in range(1, p)} for q in s: assert(p – q not in s) Both of these observations hold more generally.
If p = 1 mod 4, the residues are symmetric: n is a quadratic residue if and only if p – n is a quadratic residue.
And if p = 3 mod 4, the residues are anti-symmetric: n is a quadratic residue if and only if p – n is not a quadratic residue.
Both of these statements are consequences of the quadratic reciprocity theorem.
Quadratic excessIf you look again at the plot of residues for p = 103, you’ll notice that not only is it anti-symmetric, it is also darker on the left side.
We can verify with the following code print(len( [q for q in s if q < 51] )) print(len( [q for q in s if q > 51] )) that there are 28 residues on the left and and 23 on the right.
This is a general pattern called quadratic excess.
The quadratic excess of an odd prime p, denoted E(p) is the number of quadratic residues to the left of the middle minus the number to the right of the middle.
If p = 1 mod 4, E(p) is zero by symmetry, but if p = 3 mod 4, E(p) is always positive.
Here is a plot of quadratic excess for primes less than 3000 and congruent to 3 mod 4.
Related postsQuadratic reciprocityLegendre and Jacobi symbolsGraphing square roots modulo a prime.. More details