We work in the integers mod some odd prime $p$, and we start squaring things. It turns out that some numbers show up when we do this, and some don’t: for example, the numbers mod 5 are 0, 1, 2, 3, 4, and their squares are 0, 1, 4, 4, and 1. Since 4 shows up in this list, 4 is a square mod 5, but 2 doesn’t show up, so 2 is not a square.

If you’re given a $p$, it turns out to be relatively easy to test if a number is a square: just square everything and see if the number you’re looking for shows up. But what about the reverse problem: given a number $a$, for which primes $p$ is $a$ a square? This is the quadratic residue problem, one of the most famous problems in elementary number theory.

In this article I’ll show how to determine the primes for which the number 2 is a square, which follows a proof given in A Classical Introduction to Modern Number Theory, Ireland and Rosen. The proof relies on using complex roots of unity, which feels like a total non-sequitor after digging through a few chapters of congruences and mainly applications of classical algebra. Like all things math, I feel like this reveals some deep structure that requires a certain state of enlightenment to grasp.

Preliminaries

Looking over the first few primes see that 2 is not a square for $p = 3, p = 5, p = 11, p = 13$ but is a square for $p = 7, p = 17, p = 23$.

Let $(a / p)$ (the Legendre symbol) be 0 if $a = 0$, 1 if there is some $x$ such that $x^2\equiv a\ (p)$, and -1 otherwise. Determining when 2 is a square means determining the $p$ for which $(a / p) = 1$.

The key observation is that $a^{(p - 1)/2} \equiv (a / p)\ (p)$. This uses some group theory: every number $a^{p-1} \equiv 1\ (p)$ (Fermat’s Little Theorem), so $(a^{(p-1)/2})^2 = 1$, meaning that it can only take on two possible values modulo $p$, 1 and -1.

The Proof

Take $\zeta = e^{2\pi i / 8}$, a complex eighth root of unity which satisfies $\zeta^8 = 1$. Note that $\zeta^4 = -1$ so $\zeta^2 = -\zeta^{-2}$. Consider the expression $\zeta + \zeta^{-1}$ (this is just adding a number to its complex conjugate, so it’s a real number). Squaring this value yields $(\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2$.

(Since $\zeta$ is an algebraic integer - a root of a polynomial with integer coefficients - the concept of congruences can be shown to make sense.)

Multiplying both sides by $\zeta + \zeta^{-1}$ gives:

(This uses the simplification $(x + y)^p \equiv x^p + y^p\ (p)$ - this is possible because the binomial coefficients all being mod $p$ and so zero out.)

Next, we split into cases based on the value $p$ has congruent to 8. Since $p$ is an odd prime, it can only take on four possible values: $p \equiv 1, 3, 5, 7\ (8)$.

This gives the result:

Verifying this with Sage and choosing a random prime off a list of small primes, we see:

sage: 102929 % 8
1
sage: 2 in quadratic_residues(102929)
True


We can also verify the pattern holds for the first 100 primes:

sage: P = Primes()
sage: for i in range(0, 100):
....:     p = P.unrank(i)
....:     print(p, p % 8, 2 in quadratic_residues(p))
....:
(2, 2, False)
(3, 3, False)
(5, 5, False)
(7, 7, True)
(11, 3, False)
(13, 5, False)
(17, 1, True)
(19, 3, False)
(23, 7, True)
(29, 5, False)
(31, 7, True)
(37, 5, False)
(41, 1, True)
(43, 3, False)
(47, 7, True)
(53, 5, False)
(59, 3, False)
(61, 5, False)
(67, 3, False)
(71, 7, True)
(73, 1, True)
(79, 7, True)
...


References

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory (2nd Edition)