2 is not a square. Sure, if you are working over the field of rationals, fondly denoted **. **However** **imagine if your world is now the field of seven elements , then is very much a square ! Over , 2 is NOT a square. Here the only squares are numbers congruent to 0 or 1 mod 3.

The natural question to ask, if you are amused easily by numbers is whether there is a nice way to determine when a given number *a* is going to be a square or not modulo a given prime *p*. This is precisely what the* Legendre symbol* sets out to do.

Notes :

- The case
*p=2*is uninteresting because every number is a square mod 2, so from now on in this post we only deal with odd primes*p* - Terminology alert (!) : If
*a*is a square modulo*p*, it is called a*quadratic residue*modulo*p*

So for instance, our above number game with 2 and 7 and 3 can be written up in Legendre symbols as whereas . So depending on whether the Legendre symbol spits out 0, 1 or -1, we know whether it is a quadratic residue or not modulo the given prime.

All this is fine, but HOW do you compute ? Clearly, if *p *divides *a* we are relieved and output . If *p* does not divide *a, *the cry goes up ..*Now what ?!*

It is time to investigate some basic arithmetic that is happening over these finite fields or more generally where *p *is an odd prime.

*Question 1 : Exactly how many squares (and non-squares) are in there in , where , p an odd prime.*

This is easy to answer, 0 is a square. And if , (since *p* is odd) but Thus,

- The number of squares is given by .
- The number of non-squares is given by .

*Question 2 : How do the squares and the non-squares in interact with each other under multiplication ?*

This is again mostly easy to answer (with just a little bit of thinking). There are three cases

- A square multiplied by another square is still a square. Also (CLEAR!)
- A square multiplied by a non-square is a non-square. Also (CLEAR!)
- A non-square multiplied by a non-square is a square. Also (Er, not so clear)

The third point needs some clarification. Let *a *be a non-square (so it is not 0 for instance). Look at the map which is multiplication by *a*, that is . This is a bijection of sets (we are in a field!)

Leave 0 aside, it goes to itself under *f*. The squares go to non-squares under the map *f* (by point 2). So the non-squares HAVE TO GO TO non-zero squares under *f. *This clears up point 3. We have basically proved that the Legendre symbol multiplies !

Great, but are we any closer to actually computing ?

With a little more work, yes ! Remember that if you delete zero from a field , the rest of the elements form a (multiplicative) group of order . Thus for any nonzero *x *in the field , we have .

Let us now work with the finite field where *p *is an odd prime. Then the equation has as solutions all the non-zero quadratic residues mod *p *which are exactly in number ! So the quadratic residues are precisely the solutions to !

What happens to a non-quadratic residue mod *p* ? Well and , so it has to be the other square root of 1, namely -1. Thus, in fact, we have found an explicit formula for the Legendre symbol ! [The case when a=0 is clear.]

So for instance now we know exactly for which odd primes, *-1 *is a square.

- -1 is a square mod primes which are 1 mod 4
- -1 is NOT a square mod primes which are 3 mod 4

Let us part with the following question which we left out discussing :

*We know that in where and p is an odd prime, there are exactly squares [including 0]. What about the field of elements. How many elements of it are squares ?*

[Hint : Psst, Think Frobenius ]