Suppose we want to determine whether or not has a solution, where is prime. If is small, we could square all of the numbers mod and see if is on the list. When is large, this is impractical. If we can use the technique of the previous section and compute If has a square root, then is one of them, so we simply have to square and see if we get If not, then has no square root mod The following proposition gives a method for deciding whether is a square mod that works for arbitrary odd
Let be an odd prime and let be an integer with Then The congruence has a solution if and only if
Proof. Let Then by Fermat’s theorem. Therefore (Exercise 15),
If then The hard part is showing the converse. Let be a primitive root mod Then for some If then
By the Proposition of Section 3.7, This implies that must be even: Therefore, so is a square mod
The criterion is very easy to implement on a computer, but it can be rather difficult to use by hand. In the following, we introduce the Legendre and Jacobi symbols, which give us an easy way to determine whether or not a number is a square mod They also are useful in primality testing (see Section 9.3).
Let be an odd prime and let Define the Legendre symbol
Some important properties of the Legendre symbol are given in the following.
Let be an odd prime.
If then
If then
If then
Proof. Part (1) is true because the solutions to are the same as those to when
Part (2) is the definition of the Legendre symbol combined with the previous proposition.
To prove part (3), we use part (2):
Since the left and right ends of this congruence are and they are congruent mod the odd prime they must be equal. This proves (3).
For part (4), use part (2) with
Again, since the left and right sides of this congruence are and they are congruent mod the odd prime they must be equal. This proves (4).
Let The nonzero squares mod 11 are We have
and (use property (1))
Therefore,
The Jacobi symbol extends the Legendre symbol from primes to composite odd integers One might be tempted to define the symbol to be if is a square mod and if not. However, this would cause the important property (3) to fail. For example, is not a square mod 35, and is not a square mod 35 (since they are not squares mod 5), but also the product is not a square mod 35 (since it is not a square mod 7). If Property (3) held, then we would have which is false.
In order to preserve property (3), we define the Jacobi symbol as follows. Let be an odd positive integer and let be a nonzero integer with Let
be the prime factorization of Then
The symbols on the right side are the Legendre symbols introduced earlier. Note that if the right side is simply one Legendre symbol, so the Jacobi symbol reduces to the Legendre symbol.
Let Then
Note that 2 is not a square mod 5, hence is not a square mod 135. Therefore, the fact that the Jacobi symbol has the value does not imply that 2 is a square mod 135.
The main properties of the Jacobi symbol are given in the following theorem. Parts (1), (2), and (3) can be deduced from those of the Legendre symbol. Parts (4) and (5) are much deeper.
Let be odd.
If and then
If then
Let be odd with Then
Note that we did not include a statement that This is usually not true for composite (see Exercise 45). In fact, the Solovay-Strassen primality test (see Section 9.3) is based on this fact.
Part (5) is the famous law of quadratic reciprocity, proved by Gauss in 1796. When and are primes, it relates the question of whether is a square mod to the question of whether is a square mod
A proof of the theorem when and are primes can be found in most elementary number theory texts. The extension to composite and can be deduced fairly easily from this case. See [Niven et al.], [Rosen], or [KraftW], for example.
When quadratic reciprocity is combined with the other properties of the Jacobi symbol, we obtain a fast way to evaluate the symbol. Here are two examples.
Let’s calculate
The only factorization needed in the calculation was removing powers of 2, which is easy to do. The fact that the calculations can be done without factoring odd numbers is important in the applications. The fact that the answer is implies that 4567 is not a square mod 12345. However, if the answer had been we could not have deduced whether 4567 is a square or is not a square mod 12345. See Exercise 44.
Let’s calculate
Since 137 is a prime, this says that 107 is a square mod 137. In contrast, during the calculation, we used the fact that This does not mean that 2 is a square mod 15. In fact, 2 is not a square mod 5, so it cannot be a square mod 15. Therefore, although we can interpret the final answer as saying that 107 is a square mod the prime 137, we should not interpret intermediate steps involving composite numbers as saying that a number is a square.
Suppose is the product of two large primes. If then we can conclude that is not a square mod What can we conclude if ? Since
there are two possibilities:
In the first case, is not a square mod therefore cannot be a square mod
In the second case, is a square mod and mod The Chinese remainder theorem can be used to combine a square root mod and a square root mod to get a square root of mod Therefore, is a square mod
Therefore, if then can be either a square or a nonsquare mod Deciding which case holds is called the quadratic residuosity problem. No fast algorithm is known for solving it. Of course, if we can factor then the problem can easily be solved by computing