The Legendre symbol is a function that encodes the information about whether a number is a quadratic residue modulo an odd prime. It is used in the law of quadratic reciprocity to simplify notation. Because the Legendre symbol is so compact and has such useful properties, it is an invaluable tool for doing computations and answering questions related to quadratic residues.
- (Euler's criterion) If is an odd prime and is an integer not divisible by , then
- If , then .
- ; that is, the function is a completely multiplicative function.
- , so it is if and only if mod .
- for an odd prime , so it is if and only if mod .
- (The law of quadratic reciprocity) If and are distinct odd primes, we have
Property 1: There are two parts: first compute mod for a square, and then for not a square.
If , then mod (Fermat's little theorem) can be rewritten as mod , so mod .
Now suppose is not a square. Then note that if , there is a unique in the same range such that mod . Writing mod makes sense because every such has a unique multiplicative inverse mod Note that because is not a square. So the product of all the elements between and can be broken up into pairs of products of the form . This gives with but by Wilson's theorem, so the result follows.
Property 2 is immediate from the definition.
Property 3 follows from Property 1 and the laws of exponents.
Property 4 follows from Property 1, because if two numbers are congruent mod an odd prime and are both in , they must be equal.
Properties 5 and 6 are discussed in the quadratic reciprocity page. Notice that Property 6 can be written alternatively as
Properties 4 and 5 are often known as the first and second supplement to the law of quadratic reciprocity.
For all prime numbers where , define to be the set of all positive integers such that with and as quadratic residues modulo . For example, , because are quadratic residues modulo 11
It can be proven that is non-empty for all . Let be the smallest element of . Find the maximum value of among all .
If this maximum doesn't exist, enter 0 as your answer.
The last three properties taken together give a blueprint for an efficient computation of the Legendre symbol . Here are several examples of such computations.
Is a quadratic residue mod
Use the properties:
where the last line is by the second supplement and the fact that , so the answer is yes. Indeed, mod , but notice that the Legendre symbol computation gives no information about the solutions to mod when they exist.
This example shows the general strategy for computing using the Legendre symbol: factor the top as a product of primes, use Property 3 to separate into a product of Legendre symbols, compute the symbols using Property 5, use Property 6 to flip the other Legendre symbols, and repeat. The process terminates, and relatively quickly (with a speed similar to the Euclidean algorithm).
One potential sticking point in this process is the factoring step, if the integers involved are large enough. In fact, there is a generalization of the Legendre symbol called the Jacobi symbol that eliminates the need to factor the numerator in these computations.
For which primes is a square mod
which is if and only if mod . So the answer is this: primes congruent to mod .