# 3.10 Legendre and Jacobi Symbols

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 

# Proposition

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.

# Proposition

Let  be an odd prime.

1. If  then


2. If  then


3. If  then


4. 

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

# Example

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.

# Example

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.

# Theorem

Let  be odd.

1. If  and  then


2. If  then


3. 

4. 
5. 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.

# Example

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.

# Example

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