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