# document.write (document.title)

 Math Help > Number Theory > Squares > Quadratic Residue

. . . . . . reference other pages in the "number theory" section with many of these subjects

## Modular Arithmetic and Quadratic Equations

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

ax2 + 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 NR are there x in NR such that

x2 = a (mod R)?

The following two definitions apply only to nonzero elements of NR:  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:

 R Quadratic Residues Non-quadratic Residues 4 1 2, 3 5 1, 4 2, 3 9 1, 4, 7 2, 3, 5, 6, 8 15 1, 4, 6, 9, 10, 2, 3, 5, 7, 8, 11, 12, 13, 14

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

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

a(p-1)/2 ≡�1 (mod P). (Recall that in NP, -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 NP. 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 NP. 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 (P2-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:

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).

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.

 d Primes -6 24k+1, 5, 7, 11 -5 20k+1, 3, 7, 9 -3 6k+1 -2 8k+1, 3 -1 4k+1 2 8k±1 3 12k±1 5 10k±1 6 24k±1, 5

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 NP 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 b2 = 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 x2 = 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 = ak+1 mod P

is a solution for x2 = 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 x2 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 x2 = a mod P and x2 mod Q = a, and then using the Chinese remainder theorem to find the final result.

Thus, say we have found p in NP and q in NQ such that

p2 mod P = a and

q2 mod Q = a.

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

x2 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).

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

Arithmetic Sequence of Perfect Squares, page 3 -- If a2, b2, c2 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.

Legendre Symbol - (a/p) = 1 iff a is a quadratic residue, i.e. nonzero square, (mod p), where p is an odd prime

The webmaster and author of this Math Help site is Graeme McRae.