# 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

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 !

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

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 ]