Quadratic Residues

Modular Arithmetic and Quadratic Equations

How does one determine the solvability and the solutions of an equation such as

ax² + bx + c = 0 (mod R)

The problem boils down to the question: Which nonzero residues (mod R) have square roots (mod R)?  That is, for which a in N_R are there x in N_R such that

x² = a (mod R)?

The following two definitions apply only to nonzero elements of N_R:  If a is a nonzero residue (mod R) which has a square root (mod R), then a is said to be a quadratic residue (mod R); otherwise, a is said to be a non-quadratic residue (mod R)  (textbooks often say quadratic non-residue instead of non-quadratic residue).

It is always the case that 1 is a quadratic residue mod R; the main interest is in determining if there are any others.

Examples: 

The following theorems provide us with computational tools to determine if for odd prime number P, a given number in N_P has a square root mod P.

Theorem (Euler) Let P be an odd prime number and let a be a nonzero number in N_P. Then

a^(p-1)/2 mod P =  1, or a^(p-1)/2 mod P = P-1. (Recall that in N_P, -1 is the same thing as P-1.)

 Theorem (Euler's Criterion): Let P be an odd prime number and let a be a nonzero number in N_P. Then the following are equivalent:

1. a is a quadratic residue modulo P.
2. a^(p-1)/2 mod P = 1.

Hence we can also conclude that a is a nonquadratic residue if, and only if, a^(p-1)/2 mod P = P-1.

Legendre Symbol

The quantity a^(p-1)/2 mod P is denoted by a special symbol, called the Legendre symbol, which is

(a/P) = a^(P-1)/2 mod P.

(a/P) is 1 iff a is a quadratic residue (mod P).  The Legendre symbol has the following properties which are quite useful in computing whether one number is a quadratic residue modulo another, which is an odd prime:

Theorem: Let P be an odd prime number and let a and b be nonzero elements of N_P. Then:

1. (ab/P) = (a/P) (b/P).
2. (1/P)=1.
3. (-1/P) = (-1)^(p-1)/2.

From item 3 in the last theorem one gleans:

Corollary: Let P be an odd prime number. Then

1. (-1/P) = 1 if p mod 4 = 1, i.e. if p is a "Pythagorean Prime"
2. (-1/P) = -1 if p mod 4 = 3.

Moreover, there are for a given odd prime number P as many quadratic residues mod P as there are non-quadratic residues mod P:

Theorem: For an odd prime number P, there are (P-1)/2 quadratic residues mod P, and there are (P-1)/2 non-quadratic residues mod P.

The following important theorem is due to Gauss:

Theorem (Gauss): If P is an odd prime number, then (2/P) is equal to (-1) raised to the power (P²-1)/8.

The deepest of the results regarding quadratic residues was first proven rigorously by Gauss, and is known as the Quadratic Reciprocity Law. It states:

Quadratic Reciprocity Law

Theorem (Quadratic Reciprocity Law): Let P and Q be odd prime numbers. Then

(P/Q) (Q/P) = (-1)^{[(P-1)/2][(Q-1)/2]} .

Another way to express the quadratic reciprocity law is:

If p and q are primes, at least one of which can be expressed as 4k+1, then p is a quadratic residue (mod q) if and only if q is a quadratic residue (mod p).

If p and q are primes, both of which can be expressed as 4k+3, then p is a quadratic residue (mod q) if and only if q is not a quadratic residue (mod p).

Using the Quadratic Reciprocity Law

Alan Baker's book "A concise introduction to the theory of numbers" uses this as an example of how to use the law of quadratic reciprocity to show that (-3/p) = (p/3).  First, by quadratic reciprocity,

(p/3) (3/p) = (-1)^{[(p-1)/2][(3-1)/2]} = (-1)^(p-1)/2, so
(-1)^(p-1)/2(3/p)=(p/3).

Then, by the identities (ab/P) = (a/P) (b/P) and (-1/P) = (-1)^(p-1)/2,

(-3/p) = (-1/p)(3/p)=(-1)^(p-1)/2(3/p)=(p/3).

Now, to find the primes, p, for which -3 is a quadratic residue (mod p) -- which are also the primes, p, that are a quadratic residue (mod 3),

(p/3) = p^(3-1)/2 (mod 3) = p (mod 3)
if p = 6k+1, then p (mod 3)=1, and -3 is a quadratic residue (mod p).
but if p = 6k-1 (the only other possibility) then p (mod 3)=-1, and -3 is a quadratic nonresidue (mod p).

Primes which have a given number, d, as a quadratic residue:

Mathworld's article, Quadratic Residue includes a table giving the primes which have a given number, d, as a quadratic residue (left).  One of the many delightful fractal images (right) shows (y/x), i.e. a dot is shown if y is a quadratic residue (mod x).  The dark horizontal lines are the numbers that are square in any modulus -- 1, 4, 9, 16, ...  The diagonal lines are the squares that are between 1 and 2 times the modulus.  That is, the points for which (y/x)=1 because y+x is a square.  If you look very carefully, you can also see some steeper diagonal lines (with a slope of -2) that represent the points (y/x) for which y+2x is a square.  And, of course, the snowstorm of black dots in between these lines represent points (y/x) for which y+mx is a square, for some value of m, so in a sense, all the dots are part of some diagonal with slope -m.

How do you compute a square root mod P?

We now have a computational method for determining for an odd prime number P whether a given a in N_P is a quadratic residue mod P, or not. Once it is known that such a square root exists, one can proceed to try and find such a square root. How is this done?

A second, equally important question, is: suppose we know that a is a quadratic residue modulo the prime number P: Can we find a quadratic residue b modulo P such that b² = a mod P? And what about the case when P is a composite number?

In the case when P = 3 mod 4, or where the modulus is a product of two distinct prime numbers, each equal to 3 mod 4, there is a simple algorithm for this:

First, one solves the quadratic equation x² = a mod P for the case when P is an odd prime equal to 3 mod 4 and a is a quadratic residue mod P. The method is given in the following theorem.

Theorem: Let P be a prime number such that P mod 4 = 3. Let a be a quadratic residue mod P. Define k by (P-1)/2 = 2*k + 1. Then

x = a^k+1 mod P

is a solution for x² = a mod P. Moreover, x is a quadratic residue mod P, and is the only such solution to this equation.

Then, using the method for doing this, one solves the equation x² mod R = a where R = P*Q and P and Q are two prime numbers, each equal to 3 mod 4. This is done by first solving each of the equations x² = a mod P and x² mod Q = a, and then using the Chinese remainder theorem to find the final result.

Thus, say we have found p in N_P and q in N_Q such that

p² mod P = a and

 q² mod Q = a.

 Then we use the technique of the Chinese Remainder Theorem to compute from p and q an element x of N_R such that

x² mod R = a.

(Tonelli-Shanks algorithm)

 Internet References

Mathpages: The Jewel of Arithmetic: Quadratic Reciprocity -- Euler's Criterion for quadratic residue is that
a is a quadratic residue (mod p) iff a^(p-1)/2 = 1 (mod p).

Wikipedia: Quadratic reciprocity 

Mathworld: Quadratic Residue includes a table giving the primes which have a given number d as a quadratic residue: 

Related Pages in this website

Irrationality Proofs -- Proofs that π and e are irrational.

Pythagorean Theorem

Prove that the area of a right triangle with integer sides is not a perfect square.

Arithmetic Sequence of Perfect Squares, page 3 -- If a², b², c² are in arithmetic sequence, why is their constant difference a multiple of 24?  Look at the second answer to this question for the relationship between Pythagorean Triples and this arithmetic sequence of squares.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]