NTIC More Legendre Symbols

Section 17.1 More Legendre Symbols

Let's begin by calculating some more individual Legendre symbols. Now that we have seen a little bit of harder theory, we may appreciate some straightforward techniques that can work in lucky circumstances. (Seeing that these techniques are limited may also motivate our theoretical work in the remainder of the chapter.)

First, recall we proved the following as Proposition 16.4.7:

Proposition 17.1.1.

If \(n=ab\) is a factorization (not necessarily nontrivial) of \(n\text{,}\) then \(n\) is a QR of \(p\) precisely when either both \(a\) and \(b\) are QRs of \(p\) or both \(a\) and \(b\) are not QRs of \(p\text{.}\) In terms of Legendre symbols:

\begin{equation*} \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \end{equation*}

Example 17.1.2.

Let's try to compute \(\left(\frac{8}{19}\right)\text{.}\) Here, factoring will help;

\begin{equation*} \left(\frac{8}{19}\right)=\left(\frac{4}{19}\right)\cdot\left(\frac{2}{19}\right)\text{.} \end{equation*}

Since \(4\) is a perfect square, its symbol is one, and by Theorem 16.7.1 we know that two is not a QR modulo 19. Multiplication yields \(1\cdot -1=-1\text{,}\) so eight doesn't have a square root there either.

There is another useful computational fact that comes from the observation that \(x^2\equiv a\) (mod \(n\)) if and only if \(x^2\equiv a+n\) (mod \(n\)).

Proposition 17.1.3.

\begin{equation*} \left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right) \end{equation*}

Example 17.1.4.

What is \(\left(\frac{62}{19}\right)\text{?}\) On the one hand,

\begin{equation*} \left(\frac{62}{19}\right)=\left(\frac{62-19-19-19}{19}\right)=\left(\frac{5}{19}\right) \end{equation*}

but we don't know this yet either. On the other hand,

\begin{equation*} \left(\frac{62}{19}\right)=\left(\frac{62+19}{19}\right)=\left(\frac{81}{19}\right) \end{equation*}

Since \(81\) is a perfect square in any modulus, the symbol equals \(1\text{.}\)

We can use these ideas to calculate a lot more Legendre symbols! Here is some more practice.

Example 17.1.5.

Before continuing, alternately try each of these strategies until you either get to a perfect square or a number you already know is (or isn't) a residue. (See also Exercise 17.7.3.)

\(\displaystyle \left(\frac{55}{17}\right)\)
\(\displaystyle \left(\frac{83}{17}\right)\)
\(\displaystyle \left(\frac{45}{17}\right)\)
\(\displaystyle \left(\frac{41}{31}\right)\)
\(\displaystyle \left(\frac{27}{31}\right)\)
\(\displaystyle \left(\frac{22}{31}\right)\)

Sage note 17.1.6. Check your work.

You can always check your work, if you wish, using Sage.

It turns out you can resolve some theoretical questions with these techniques.

Fact 17.1.7.

There are always consecutive quadratic residues for \(p>5\text{.}\)

Proof.

First, we know that \(1,4,9\) are all quadratic residues. Thus, if at least one of \(2,5,10\) was also a QR, then we could guarantee that there were always consecutive quadratic residues somewhere!

As it turns out, if \(p=5\) this doesn't work, because the only (nonzero) QRs are \(\pm 1\) for that prime. But if \(p=7\text{,}\) then \(a=1\) and \(a=9\equiv 2\) are consecutive.

Now suppose \(p>7\) is prime. Then at least one of \(2,5,10\) must be a QR, since one of these things must be true:

2 could be a QR
5 could be a QR
If 2 and 5 both aren't, then the computation

\begin{equation*} \left(\frac{10}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{5}{p}\right)=(-1)(-1)=1 \end{equation*}

means 10 is a QR!

Thus we see that calculation and theory must go hand in hand; they are not separate.