What is the point of quadratic residues?

Question

What is the most motivating way to introduce quadratic residues? Are there any real life examples of quadratic residues? Why is the Law of Quadratic Reciprocity considered as one of the most important in number theory?

Answer 1

Warning: these are pure math examples of why we like quadratic residues, not real life.

Well, this is more quadratic residues than quadratic reciprocity, but the computation of $\left(\frac{-1}p\right)$ and $\left(\frac{-3}{p}\right)$ (those are Legendre symbols) are essential to determining when primes in the natural numbers are prime in the Gaussian integers ($\Bbb Z[i]$) and the Eisenstein Integers ($\Bbb Z[e^{2\pi i/3}]$). They are furthermore necessary for the proof of when numbers are expressible as $a^2+b^2$ or $a^2+ab+b^2$ for $a,b\in\Bbb Z$. The two-square proof is also extendible to Lagrange's Four Square Theorem, which also uses quadratic residues.

---

There is also a pretty cool relationship between Jacobi symbols and permutations which is that if you write the action of multiplication on a ring $\Bbb Z/n\Bbb Z$ by $a$ in cycle notation (e.g. $2\cdot \Bbb Z/9\Bbb Z$: $$ \{0,1,2,3,4,5,6,7,8\}\to\{0,2,4,6,8,1,3,5,7\}=(0)(124875)(36) $$) then the sign of the permutation (where sign is defined to be $(-1)^{n}$ where $n$ is the number of $2$-cycles the permutation decomposes into) is equal to $\left(\frac an\right)$, where that is the Jacobi symbol.

Stated more concisely: $\text{sgn}(a\cdot(\Bbb Z/n\Bbb Z))=\left(\frac an\right)$ where $a\cdot(\Bbb Z/n\Bbb Z)\in S_n$.

---

Lastly, I'll refer you to this mathSE post which has a lot of good answers to a similar question.

Answer 2

Quadratic reciprocity is important because it provides a bridge between two apparently distinct branches of mathematics, namely the theory of Galois representations and the theory of automorphic forms. $L$-functions provide the bridge across the two theories.

Let $K=\mathbf Q(\sqrt{D})$ be a quadratic field with fundamental discriminant $D$. Let $G=\text{Gal}(K/\mathbf Q)$. The group $G=\left<\sigma\right>$ is cyclic of order $2$, and therefore it has two irreducible complex representations, both of dimension $1$: the trivial one, and the one $\sigma \mapsto -1$. If $\rho$ is this last representation, then the splitting of primes in $K$ is encoded by $\rho$ via the Frobenius, namely whenever $(p, D)=1$, we have $\rho(\text{Frob }p) = +1$ if $p$ splits in $K$ and $-1$ if it is inert. According to Quadratic Reciprocity, the Artin $L$-function $L(\rho, s)$ is equal to the Dirichlet $L$-function $L(\chi, s)$, for $\chi$ the primitive quadratic Dirichlet character of modulus $D$. Thus, we have an example of an $L$-function of an algebraic object (the Galois representation $G_{\mathbf Q} \to G \xrightarrow{\rho} \pm 1$) which is equal to the $L$-function of an analytic object (essentially the theta function $\theta(\chi, q)$ attached to $\chi$).

This means that the description of the splitting of primes in $K$, while apparently an infinite amount of information, can actually be determined by a finite amount of information (knowledge of the character $\chi$).

Answer 3

Quadratic reciprocity is important if you are cutting an 8x8 pan of brownies into very small square pieces for 21 friends and you want to know if you can give them all the same amount and have exactly five pieces left for yourself.

Answer 4

I always like to motivate them through the want to solve Diophantine equations.

If I challenge someone to solve any of these nasty equations over the integers:

$x^2 + 440xy^{45} + 88x^{57} = 3$

$48x^5 + y^2 + 3000z^{34} = 17$

$55x^4 + 60xy^3 + 50001z^2 = 1532877192878$

then you will surely struggle by using elementary means. In each case you could set up a brute force search and get no solutions but of course this isn't really a proof.

However you notice that if there were any solutions to these then you could reduce each equation mod $4,3,5$ respectively and would be left solving:

$x^2 = 3 \bmod 4$

$y^2 = 2 \bmod 3$

$z^2 = 3 \bmod 5$

and these really ARE things we can show have no solutions very easily! It only takes a finite amount of searching to find quadratic residues. The great thing here is that I could have changed most of the coefficients above by multiples of $4,3,5$ and still had no solutions.

The power of modular arithmetic is amazing.

Another nice little result is that no number that is $3 \bmod 4$ can ever be a sum of two square numbers. Why is this? Well if $n \equiv 3 \bmod 4$ and $x^2 + y^2 = n$ then looking mod $4$ the LHS would have to be $0,1$ or $2$ (since the quadratic residues mod $4$ are $0,1$) yet the RHS would be $3 \bmod 4$!

Answer 5

Let $p$ be an odd prime. Below, $a, b, c$ are integers.

Simple modular arithmetic tells you when $ax + b \equiv 0 \pmod p$, $a \not\equiv 0 \pmod p$, has a solution (namely, always). What about $ax^2 + bx + c \equiv 0 \pmod p$, $a \not\equiv 0 \pmod p$?

As $4a \not\equiv 0 \pmod p$, we can multiply by $4a$ without changing the solutions. This yields $4a^2x^2 + 4abx + 4ac \equiv 0 \pmod p$. By completing the square, we can rewrite this as $(2ax + b)^2 \equiv b^2 - 4ac \pmod p$. Letting $y = 2ax + b$ and $d = b^2 - 4ac$, we see that any quadratic $ax^2 + bx + c$, when considered modulo $p$, can be reduced to the form $$y^2 \equiv d \pmod p.$$

This equivalence has a solution if and only if $d$ is a quadratic residue of $p$. In particular, $ax^2 + bx + c \equiv 0 \pmod p$ has a solution if and only if the discriminant is a quadratic residue modulo $p$.

For this reason, I view quadratic residues as an indication of when I can solve a quadratic equation modulo $p$ (or equivalently, in the field $\mathbb{Z}_p = \mathbb{Z}/p\mathbb{Z}$).

Answer 6

Quadratic sieve is an example of an algorithm that requires the computation of a quadratic residue. It's a basic factoring algorithm that requires solving multiple instances of $Y(x) \equiv 0 \equiv (x + s)^2 - N \pmod p$. All instances have the same $N$ and $s$ value, you are solving for $x$ and $p$. Solutions require $p$ to be a quadratic residue of $N$.