We work in the integers mod some odd prime , 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 , 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 , for which primes is 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.
Looking over the first few primes see that 2 is not a square for but is a square for .
Let (the Legendre symbol) be 0 if , 1 if there is some such that , and -1 otherwise. Determining when 2 is a square means determining the for which .
The key observation is that . This uses some group theory: every number (Fermat’s Little Theorem), so , meaning that it can only take on two possible values modulo , 1 and -1.
Take , a complex eighth root of unity which satisfies . Note that so . Consider the expression (this is just adding a number to its complex conjugate, so it’s a real number). Squaring this value yields .
(Since 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 gives:
(This uses the simplification - this is possible because the binomial coefficients all being mod and so zero out.)
Next, we split into cases based on the value has congruent to 8. Since is an odd prime, it can only take on four possible values: .
This gives the result:
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) ...
- Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory (2nd Edition)