NTIC Introducing the Legendre Symbol

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 [C.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³Unfortunately, despite the suggestion of “a on p” for pronouncing it, there does not seem to be a standard way to read this aloud..)

🔗

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 Fact 16.1.2: We have that $\left(\frac{-1}{p}\right)=1$ for $p$ prime if and only if $p=2$ or $p\equiv 1$ (mod $4$ ).

🔗

The command in Sage is pretty straightforward. We use it, and then demonstrate it via an interact.

xxxxxxxxxx
 
legendre_symbol(-2,11)

xxxxxxxxxx
 
@interact
def _(p=(17,prime_range(50))):
    for n in [q for q in quadratic_residues(p) if q != 0]:
        pretty_print(html(r"$%s$ is a QR of $%s$ and $\left(\frac{%s}{%s}\right)=%s$"%(n, p, n,p, legendre_symbol(n,p))))

🔗

Remark 16.6.3.

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 prime? (As usual, you can do this by hand for small primes if you aren't computing.)

xxxxxxxxxx
 
@interact
def _(p=(19,prime_range(100))):
    L = [legendre_symbol(a,p) for a in [0..p-1]]
    pretty_print(html(r"All Legendre symbols $\left(\frac{a}{%s}\right)$ can be listed:"%p))
    print(L)
    pretty_print(html("And they sum up to $%s$"%sum(L)))

🔗

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 [C.4.6, Exercise 9.7].)