Quadratic Reciprocity

I just read a most interesting article in Quanta Magazine about the new Fields medallist Peter Scholze. His discoveries are quite beyond my comprehension but in the article mention is made of quadratic reciprocity. I've come across the concept repeatedly but have always avoided taking the time to understand it. However, in this article it was explained simply and clearly. 

Reciprocity laws are generalisations of the 200-year-old quadratic reciprocity law, a cornerstone of number theory and one of Scholze’s personal favourite theorems. The law states that given two prime numbers p and q, in most cases p is a perfect square on a clock with q hours exactly when q is a perfect square on a clock with p hours. For example, five is a perfect square on a clock with 11 hours, since \(5 = 16 = 4^2 \), and 11 is a perfect square on a clock with five hours, since \(11 = 1 = 1^2 \).

Here is a more detailed explanation of quadratic reciprocity (source):

It's easy to find integer solutions of the equation \( y^2 = 2x^2 + 7k \), but there are no integer solutions at all of the seemingly similar equation \( y^2 = 3x^2 + 7k \).  This is the sort of thing that experienced number theorists can tell at a glance, simply by noting that the equations written modulo 7 are \( y^2 = 2x^2 \) and \( y^2 = 3x^2 \) respectively, and since division is unique in the field of integers (mod p) we have \( (y/x)^2 \equiv n \pmod{p} \), which implies that n must be the square of some element of the field of integers modulo p.  But the integers mod 7 are just 0, 1, 2, 3, 4, 5, 6, whose squares (mod 7) are 0, 1, 4, 2, 2, 4, 1. Thus the equation \( y^2 = nx^2 + 7k \) can have integer solutions only if n is congruent to 0, 1, 2, or 4 (mod 7).  These are called the quadratic residues (mod 7), and the remaining numbers 3, 5, 6 are called the non-quadratic residues.  

It's often extremely important when dealing with problems in number theory to know whether a certain prime p is a square (i.e., a quadratic residue) modulo some other particular prime q. Legendre defined a symbol to represent this information, which we will denote as

This is a remarkable fact, and not at all self-evident.  Legendre succeeded in proving some special cases of this, and also gave what he thought was a complete proof, but his argument relied on the premise that every arithmetic progression contains infinitely many primes. This is in fact true, as subsequently shown by Dirichlet, but at the time of Legendre's proof it wasn't known, so Gauss pointed out that Legendre's proof was incomplete. Gauss went even further, and gave several (valid) proofs of this remarkable theorem, which he called the Fundamental Theorem of number theory.

Thus [p\q] equals either +1 or -1 depending on whether p is or isn't a square modulo q. From examining many individual cases, Euler had previously noticed a striking relationship between the [p\q] and [q\p].  Specifically, he noticed that [p\q] = [q\p] except when p and q are both of the form 4k-1, in which case [p\q] = -[q\p]. 

Let's take a specific example. Yesterday I turned 25339 days old. The previous prime is 25321. It can seen that \( 25339 \equiv 18 \pmod{25321} \) and \( 25321 \equiv 25321 \pmod{253339} \), neither residue being square. Therefore \([25339\25321] = [25321\25339] = -1\). Note that 25321 is a 4k+1 prime while 25339 is a 4k-1 prime, which is in accord with the theorem.

I've download a PDF titled Quadratic Residues and Non-Residues Selected Topics by Steve Wright from the Department of Mathematics and Statistics Oakland University, Rochester, Michigan and dated 21st October 2106. It's freely available here. I'll have a read over this and see if I can deepen my understanding of this topic.

Here are some SAGE commands that can be used when dealing with quadratic residues (double click to enlarge):

Source: http://doc.sagemath.org/html/en/constructions/number_theory.html

ADDENDUM:

When trying to tackle the above Quadratic Residues and Non-Residues Selected Topics, I quickly realised that my foundations in modular arithmetic were a little shaky and needed to be reinforced a little. I began watching a series of videos by Polar Pi on YouTube, beginning with this video on a linear congruence equation with one solution:

The next video in this series relates to linear congruence equations with multiple solutions and the third of the three videos looks at linear congruence equations with no solutions.

The YouTube channel blackpenredpen has some videos on modular arithmetic as well:

• What does a ≡ b (mod n) mean? Basic Modular Arithmetic, Congruence? Link
• Solving congruences, 3 introductory examples. Link
• System of congruences, modular arithmetic. Link