Skip to main content
Logo image

Number Theory: In Context and Interactive

Karl-Dieter Crisman

Section 16.6 Introducing the Legendre Symbol

Consider the lowly notion of congruence, along with its symbol \(\equiv\text{.}\) It is easy to explain; yet Gauss revolutionized number theory and made it more accessible to others with it.
In Legendre’s research into questions of residues, he discovered that certain powers were always either \(\pm 1\text{,}\) omitting multiples of what we would today call the modulus. Some of what he found was essentially Theorem 16.5.2. This enabled the great innovation of Legendre’s we alluded to earlier.
What of the plus or minus 1; why is this so innovative? To quote an article [E.7.5] on this subject, if one has a symbol for it, it becomes
… more than a notational convenience … Legendre reifies this concept, and makes it into an object of independent study.
―Steven H. Weintraub
In our modern terms, Legendre takes advantage of the fact that \(a=g^i\) is an even power exactly when \(a\) is a QR, and \((-1)^i=1\) precisely when \(i\) is even (and hence precisely when \(a\) is a QR). This is the so-called Legendre symbol. (However, he did not use the term QR, just the symbol 9 .)

Definition 16.6.1.

We write \(\left(\frac{a}{p}\right)\) for the Legendre symbol. Given that \(p\) is an odd prime, for \(a\) coprime to \(p\) we set
\begin{equation*} \left(\frac{a}{p}\right)=1\text{ if }a\text{ is a QR modulo }p\text{, and }\left(\frac{a}{p}\right)=-1\text{ otherwise.} \end{equation*}
We define the Legendre symbol of \(a\) modulo \(p\) to be zero if \(p\mid a\text{.}\)

Example 16.6.2.

We can now restate the main content of Fact 16.1.2: For odd \(p\text{,}\) we have that \(\left(\frac{-1}{p}\right)=1\) if and only if \(p\equiv 1\) (mod \(4\)).

Example 16.6.3.

We can also restate Example 16.5.4 as \(\left(\frac{2}{17}\right)=1\) and \(\left(\frac{3}{17}\right)=-1\text{.}\)
The command in Sage is pretty straightforward. We use it, and then demonstrate it via an interact.

Remark 16.6.4.

A brief note is in order regarding the special status of zero in Definition 16.3.1, especially since Sage includes zero as a QR.
First, this recognizes the special case that only \(0^2=0\text{,}\) while \(1=1^2=(-1)^2\) (and everything else) usually have two square roots modulo a prime.
A deeper reason is that this status allows us to conveniently ignore the only integer from \(0\) to \(p-1\) which is not in \(U_p\text{.}\) In fact, the multiplicative property Proposition 16.4.7 ensures you can consider \(x\mapsto \left(\frac{x}{p}\right)\) to be a function from \(U_p\) to \(\{1,-1\}\) of the kind we call a group homomorphism. (Indeed, it gets us from a cyclic group of order \(p-1\) to a cyclic group of order \(2\text{,}\) with “kernel” the cyclic subgroup of order \((p-1)/2\) that we already mentioned in Theorem 16.4.3.)
Here’s a final introductory experiment with Legendre symbols. What is the sum of all Legendre symbols for a given (odd) prime? (As usual, you can do this by hand for small primes if you aren’t computing.)
This is cool, and a nice example of the kind of fun one can have experimenting. What do you think? Do you think we can prove it? Try doing so in Exercise 16.8.8. (For harder exercises of this type, see [E.4.6, Exercise 9.7].)
Unfortunately, despite the suggestion on mathoverflow.net/questions/15447 of “a on p” for pronouncing it, there does not seem to be a standard way to read this aloud.
<Prev^TopNext>