Quadratic Residues
Sometimes we might be interested in the question of whether certain numbers are congruent to the square of some other number modulo a prime. One option to answer this question is trial and error, for instance the question of whether 3 is congruent to the square of a number mod 7: We can see that there’s no 3 here in this table. What I love about Silverman is that he has us “experiment” with different numbers to really see the patterns we care about. So in the spirit of this we can try another example. 1, 2, and 4 are Quadratic Residues (QR), while 3, 5, and 6 are Non-residues (NR). 3 is not a square mod 7. In our p=11 experiment, Quadratic Residues are 1, 3, 4, 5, 9. The Quadratic Non-Residues are 2, 6, 7, 8, 10. If you were a number living in the world of Modulo 11, and you were a 7, you could never be the result of a square. You are an impossible value. So in a nutshell, that’s what quadratic residues are. Easy enough to understand, but why do we care about them? This is one of those...