To begin with, let's get some more intuition by trying to calculate some more Legendre symbols. Remember, we have several interesting properties, including a sort of multiplicativity and Euler's criterion. In the previous chapter we proved the following:

In terms of Legendre symbols, it means \[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]

It is also true that \(x^2\equiv a\) mod (\(n\)) if and only if \(x^2\equiv a+n\) mod (\(n\)), which means that we can look at whatever residue of \(a\) is convenient, or \[\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)\]

So we can use these ideas to calculate! 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.

• \(\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)\)

It turns out you can resolve theoretical questions this way too.

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