To begin with, let's get some more intuition by trying to calculate some more Legendre symbols. Remember, we have several interesting basic properties, not just Euler's criterion. In the previous chapter we proved the following as Proposition 16.5.3:
If \(n=ab\) is a factorization (not necessarily nontrivial) of \(n\), 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\). (Hence if one of \(a,b\) is and the other isn't, neither is \(n\).)
In terms of Legendre symbols, it means \begin{equation*}\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\end{equation*}
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\)).
\begin{equation*}\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)\end{equation*}
So we can use these ideas to calculate a lot more Legendre symbols!
Let's compute a few this way.
What is \(\left(\frac{62}{19}\right)\)? 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 regardless, this equals \(1\).
Let's try \(\left(\frac{8}{19}\right)\). Here, factoring will help; \begin{equation*}\left(\frac{8}{19}\right)=\left(\frac{4}{19}\right)\cdot\left(\frac{2}{19}\right)\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, so we get \(1\cdot -1=-1\) and eight doesn't have a square root there either.
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.)
\(\left(\frac{55}{17}\right)\)
\(\left(\frac{83}{17}\right)\)
\(\left(\frac{45}{17}\right)\)
\(\left(\frac{41}{31}\right)\)
\(\left(\frac{27}{31}\right)\)
\(\left(\frac{22}{31}\right)\)
You can always check your work, if you wish, using Sage.
It turns out you can resolve theoretical questions this way too.
There are always consecutive quadratic residues for \(p>5\).
Thus we see that calculation and theory must go hand in hand; they are not separate.
