Distribution of quadratic residues

Let p be an odd prime number. If the equation

x² = n mod p

has 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-symmetry

If 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 pn is a quadratic residue. And if p = 3 mod 4, the residues are anti-symmetric: n is a quadratic residue if and only if pn is not a quadratic residue. Both of these statements are consequences of the quadratic reciprocity theorem.

```   print(len( [q for q in s if q < 51] ))