Section17.1More Legendre Symbols

Subsection17.1.1Keep Computing

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)\)
Remark17.1.2

Sage note:
Check your work if you want.

Subsection17.1.2Some Theory

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.