elementary number theory

The Legendre symbol

2 is not a square. Sure, if you are working over the field of rationals, fondly denoted \mathbb{Q}. However imagine if your world is now the field of seven elements \mathbb{F}_7, then 2=3^2 is very much a square ! Over \mathbb{F}_3, 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 :

  1. 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
  2. Terminology alert (!) : If is a square modulo p, it is called a quadratic residue modulo p

Screen Shot 2014-11-19 at 8.37.44 AM

So for instance, our above number game with 2 and 7 and 3 can be written up in Legendre symbols as \left(\frac{2}{7}\right)= 1 whereas \left(\frac{2}{3}\right)= -1. 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 \left(\frac{a}{p}\right) ? Clearly, if divides a we are relieved and output \left(\frac{a}{p}\right)=0. 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 \mathbb{F}_p or more generally \mathbb{F}_{p^n} where is an odd prime.

Question 1 : Exactly how many squares (and non-squares) are in there in \mathbb{F}_q, where q=p^n, p an odd prime.

This is easy to answer, 0 is a square. And if a\neq 0\in \mathbb{F}_q, a\neq -a (since p is odd) but a^2 = (-a)^2 Thus,

  1. The number of squares is given by 1+\frac{q-1}{2} = \frac{q+1}{2} = \frac{p^n+1}{2}.
  2. The number of non-squares is given by q-\frac{q+1}{2} = \frac{q-1}{2}= \frac{p^n-1}{2}.

Question 2 : How do the squares and the non-squares in \mathbb{F}_q interact with each other under multiplication ?

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

  1. A square multiplied by another square is still a square. Also 1\times 1 = 1 (CLEAR!)
  2. A square multiplied by a non-square is a non-square. Also 1\times -1 = -1 (CLEAR!)
  3. A non-square multiplied by a non-square is a square. Also -1 \times -1 = 1 (Er, not so clear)

The third point needs some clarification. Let be a non-square (so it is not 0 for instance). Look at the map which is multiplication by a, that is f : \mathbb{F}_q \to \mathbb{F}_q, x\leadsto ax. This is a bijection of sets (we are in a field!)

Leave 0 aside, it goes to itself under f. The \frac{q-1}{2} squares go to \frac{q-1}{2} non-squares under the map f (by point 2). So the \frac{q-1}{2} 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 !

Screen Shot 2014-11-19 at 8.38.06 AM

Great, but are we any closer to actually computing \left(\frac{a}{p}\right) ?

With a little more work, yes ! Remember that if you delete zero from a field \mathbb{F}_q, the rest of the elements form a (multiplicative) group of order q-1. Thus for any nonzero in the field \mathbb{F}_q , we have x^{q-1}=1.

Let us now work with the finite field \mathbb{F}_p where is an odd prime. Then the equation x^{\frac{p-1}{2}}=1 has as solutions all the non-zero quadratic residues mod which are exactly \frac{q-1}{2} in number ! So the quadratic residues are precisely the solutions to x^{\frac{p-1}{2}}=1 !

What happens to a non-quadratic residue mod p ? Well a^{p-1}=1 and a^{\frac{p-1}{2}}\neq 1, 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.]

Screen Shot 2014-11-19 at 8.38.18 AM

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 \mathbb{F}_q where q=p^n and p is an odd prime, there are exactly \frac{q+1}{2} squares [including 0]. What about the field \mathbb{F}_{2^n} of 2^n elements. How many elements of it are squares ?

[Hint : Psst, Think Frobenius ]