The law of quadratic reciprocity is a beautiful result. It is also an excellent tool to answer the question: given an odd prime , and given that is an integer such that and are relatively prime, is is a quadratic residue modulo , in other words, is the equation solvable? Using the law of quadratic reciprocity requires the evaluation of the Legendre symbol. The focus of this post is on the Legendre symbol as well as related concepts of quadratic residues and the law of quadratic residues. The versatility of the law of quadratic reciprocity is demonstrated with examples.
The setting is that the modulus in question is an odd prime . Consider an integer such that and are relatively prime, i.e. having no common prime factor. The number is said to be a quadratic residue modulo if the equation has an integer solution in . Another way to say this is that is a quadratic residue modulo if there exists a square root of modulo (a square root would be a solution to the equation). If the integer is not a quadratic residue modulo , we say that is a quadratic nonresidue modulo . If the context is clear, the word quadratic can be omitted. We can then say is a residue modulo or is a nonresidue modulo .
Since every integer is congruent modulo to one of the numbers in the set , the integers can be considered from the set (the non-zero elements of ).
Let’s look at a quick example. Let . Squaring each number in produces the set . Reducing modulo 11 produces the set . Thus the integers 1, 3, 4, 5 and 9 are quadratic residues modulo 11. The square roots of each residue are the solutions to the equation . For , the solutions are x = 5 and 6. There are two square roots of 3 modulo 11, namely 5 and 6.
When the modulus is small, it is easy to find all quadratic residues simply by squaring all the numbers in . The focus in this post is on how to use the law of quadratic reciprocity to determine whether a given is a quadratic residue modulo a large odd prime .
To check whether the integer is a quadratic residue modulo an odd prime , the most important idea, before considering the law of reciprocity, is to check the modular exponentiation . If the result is congruent to 1 modulo , then is a quadratic residue modulo . If the result is congruent to -1 modulo , then is a quadratic nonresidue modulo . This is called Euler’s Criterion (proved here). For clarity, it is stated below.
Theorem 1 (Euler’s Criterion)
Let be an odd prime. Let be an integer that is relatively prime to . Then the integer is a quadratic residue modulo if and only if . On the other hand, the integer is a quadratic nonresidue modulo if and only if .
According to Euler’s Criterion, the task of checking for the status of quadratic residue is a matter of performing a modular exponentiation. This can be done using software or a calculator for modular arithmetic. If so desired, the exponentiation can also be programmed using the fast powering algorithm.
Though Euler’s Criterion (with a calculator for modular arithmetic) is a sure fire way for checking the status of quadratic residues, the law of quadratic reciprocity can simplify the task even further. As the examples below will show, checking the status of quadratic residues using the law of reciprocity may require no modular exponentiation at all and if exponentiation is required, it is of a much smaller size.
Euler’s Criterion also gives us several basic facts about quadratic residues.
Let be an odd prime. The following properties are true:
- If and are both residues modulo , then the product is a residue modulo .
- If If and are both nonresidues modulo , then the product is a residue modulo .
- If and are such that one of them is a residue modulo and the other is a nonresidue modulo , then the product is a nonresidue modulo .
Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime . The product of two integers of different types is always a nonresidue modulo the odd prime . The theorem follows from Euler’s criterion and from the fact that .
In arithmetic modulo a prime , there exists a primitive root modulo and that any primitive root generates by powering all the integers that are relatively prime to the modulus . Let be a primitive root modulo an odd prime . It then follows that the quadratic residues modulo are the even powers of and the nonresidues are the odd powers of . A related fact is that when is an odd prime and when and are relatively prime, the equation either has two solutions or has no solutions.
Let be a primitive root modulo an odd prime . For any that is relatively prime to , the following is true:
- is a quadratic residue modulo if and only if is of the form for some positive integer ,
- is a quadratic nonresidue modulo if and only if is of the form for some positive integer .
Let be an odd prime. For any that is relatively prime to , the equation either has two solutions or has no solutions (proved here).
The law of quadratic reciprocity is stated using the Legendre symbol. For an odd prime and for an integer that is relatively prime to , the symbol is defined as follows:
One obvious and important observation is that Euler’s Criterion can be restated as follows:
Theorem 1a (Euler’s Criterion)
Let be an odd prime. Let be an integer that is relatively prime to . Then .
In the above definition, the lower argument of the Legendre symbol is always an odd prime and the upper argument is an integer that is relatively prime to the lower argument. To smooth out some statements involving the Legendre symbol and to make it easier to define the Jacobi symbol in the next post, we relax the Legendre symbol by making whenever and are not relatively prime, i.e. . The Legendre symbol can be broaden slightly by the following:
Here’s some useful basic facts about the Legendre symbol.
Let be an odd prime. The following properties hold:
- The Legendre symbol is periodic with respect to the top argument, i.e. if , then .
- The Legendre symbol is multiplicative with respect to the top argument, i.e. .
- If , then . If , then .
The first bullet point in Theorem 5 is easily verified based on the definition of the Legendre symbol. For the case , the other facts in Theorem 5 are easily verified. For the case , the second bullet point follows from Theorem 2, i.e. the fact that the product of two residues and the product of two nonresidues are both residues modulo an odd prime and that the product of a residue and a nonresidue is a nonresidue modulo an odd prime. The second part of the third bullet point is true since any integer that is a square is a quadratic residue.
Law of Quadratic Reciprocity
The law of reciprocity can ease the calculation of the Legendre symbol when both the upper and lower arguments are distinct odd primes. Theorem 6 is the law of reciprocity and Theorem 7 and Theorem 8 are two supplements to the law that can round out the calculation. After stating the theorems, we demonstrate with some examples.
Theorem 6 (the law of quadratic reciprocity)
Let and be two distinct odd prime numbers. Both of the following statements hold.
Equivalently and more explicitly,
Theorem 7 (first supplement to the law of quadratic reciprocity)
Let be an odd prime number. The following statement holds.
Theorem 8 (second supplement to the law of quadratic reciprocity)
Let be an odd prime number. The following statement holds.
Theorem 6 shows how to flip the Legendre symbol if both the upper and lower arguments are distinct odd primes. As long as one of the primes is congruent to 1 modulo 4, we can safely flip the symbol. If both primes are not congruent to 1 modulo 4, we can still flip the symbol except that we have to attach a minus sign. Theorem 7 (the first supplement) indicates when -1 (or ) is a quadratic residue an odd prime . In words, -1 is a residue modulo if dividing by 4 gives the remainder of 1. Otherwise -1 is a nonresidue modulo . Theorem 8 (the second supplement) indicates when 2 is a residue modulo an odd prime . In words, 2 is a residue modulo if dividing by 8 leaves a remainder of 1 or 7. Otherwise 2 is a nonresidue modulo .
Evaluate , an example where both the upper and lower arguments in the Legendre symbol are primes.
The above derivation is a repeated use of Theorems 5, 6 and 8. The idea is to flip the Legendre symbols to make the lower arguments smaller. Then reduce the upper arguments and then factor the upper arguments. Then flip again until reaching a Legendre symbol of , which is easy to solve.
It then follows that 1783 is a quadratic residue modulo the odd prime 7523. The answer can be confirmed by using Euler’s Criterion. Note that .
Evaluate where 1298351, an odd prime and 756479.
The number is not a prime and is factored as . We have the following derivation.
The evaluation of the Legendre symbols in this example does not start with a flipping since the upper argument 756479 is not a prime. Instead, we start with factoring the upper argument into prime factors and then proceed with a series of flipping, reducing and factoring.
Evaluate where 569, an odd prime and 1610280.
This example can also be evaluated by first reducing 1610280 modulo 569.
The law of quadratic reciprocity is a deep and powerful result. It guides the evaluation of Legendre symbols in an attempt to answer whether a number is a quadratic residue modulo an odd prime. The law of reciprocity as represented above requires that the lower argument in the Legendre symbol is an odd prime. When the upper argument is an odd number that is not a prime, there is no way to flip it (based on the law of reciprocity using the Legendre symbol). In Example 2, the evaluation of the Legendre symbol cannot begin until the top argument is factored. The factoring in Example 2 is possible since the number is small. When the number is large, factoring may not always be feasible. It turns out that the Legendre symbol has a generalization, called the Jacobi symbol, that is even more versatile and is defined in the next post.