Introducing Quadratic Residues: Real World Examples & Law of Reciprocity

[matqkks]

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?

 

[mathbalarka]

(I don't know an answer to the first one, not being a teacher in any respect)

This is an interesting question. I don't recall any direct consequence(s) of it, but thinking of a more general Langland programs, for example, although the consequences are complicated.

The law of quadratic residues is one of the non-trivial results in elementary number theory. Several results of algebraic and analytic number theory lies on this theorem. In fact, there are some open conjectures regarding a smooth generalization of this result, take for example, Hilbert's 9-th problem.

 

[Deveno]

Here is one aspect of quadratic residues I always found fascinating:

Consider the field $\Bbb Z_p$.

Since this *is* a field, its group of units is precisely the set of non-zero elements, $\Bbb Z_p^{\ast}$.

Since this is a finite group, any subset closed under multiplication is a subgroup.

If we denote the set of (non-zero) quadratic resides by $R$, it is clear $R$ is a subgroup of the group of units since if:

$x,y \in R$, we have $x = a^2, y = b^2$ for some $a,b \in \Bbb Z_p^{\ast}$, thus:

$ab \in \Bbb Z_p^{\ast}$ (since any field is, of course, an integral domain), and:

$xy = (a^2)(b^2) = (ab)^2 \implies xy \in R$ (because multiplication in $\Bbb Z_p^{\ast}$ is commutative).

From the above, it should be clear that the map $\phi: x \to x^2$ is a surjective group homomorphism from $\Bbb Z_p^{\ast} \to R$. A natural question to ask, then, is: what is its kernel?

Clearly $1$ is the identity of $R$ ($1 \in R$ since $1 = 1\ast1 = 1^2$). Thus finding the kernel is the same as finding the roots of $x^2 - 1$ in $\Bbb Z_p^{\ast}$. Since $\Bbb Z_p$ is a field, and $x^2 - 1 \in \Bbb Z_p[x]$, we know this equation can have at most 2 roots. In fact, if $p \neq 2$, we have EXACTLY two roots: 1 and -1 (= p-1).

So for an odd prime $p$, group theory tells us that:

$[\Bbb Z_p^{\ast}:R] = |\text{ker}(\phi)| = 2$, that is:

$|R| = \frac{p-1}{2}$.

This, in effect, let's us choose "positive" elements of a finite field: just as in the case of real numbers, the "positive" elements are the ones that be written as the square of another (non-zero) element of the field. The rules for the cosets $R$ and $-R$ are the same as the rules we learned for positive and negative real numbers under "ordinary" multiplication:

$R\ast R = R$
$R \ast -R = -R \ast R = -R$
$-R \ast -R = R$.

This allows us to use "parity" arguments in some cases, saving time and sometimes considerable calculation.

 

[caffeinemachine]

Here is one aspect of quadratic residues I always found fascinating:

Consider the field $\Bbb Z_p$.

Since this *is* a field, its group of units is precisely the set of non-zero elements, $\Bbb Z_p^{\ast}$.

Since this is a finite group, any subset closed under multiplication is a subgroup.

If we denote the set of (non-zero) quadratic resides by $R$, it is clear $R$ is a subgroup of the group of units since if:

$x,y \in R$, we have $x = a^2, y = b^2$ for some $a,b \in \Bbb Z_p^{\ast}$, thus:

$ab \in \Bbb Z_p^{\ast}$ (since any field is, of course, an integral domain), and:

$xy = (a^2)(b^2) = (ab)^2 \implies xy \in R$ (because multiplication in $\Bbb Z_p^{\ast}$ is commutative).

From the above, it should be clear that the map $\phi: x \to x^2$ is a surjective group homomorphism from $\Bbb Z_p^{\ast} \to R$. A natural question to ask, then, is: what is its kernel?

Clearly $1$ is the identity of $R$ ($1 \in R$ since $1 = 1\ast1 = 1^2$). Thus finding the kernel is the same as finding the roots of $x^2 - 1$ in $\Bbb Z_p^{\ast}$. Since $\Bbb Z_p$ is a field, and $x^2 - 1 \in \Bbb Z_p[x]$, we know this equation can have at most 2 roots. In fact, if $p \neq 2$, we have EXACTLY two roots: 1 and -1 (= p-1).

So for an odd prime $p$, group theory tells us that:

$[\Bbb Z_p^{\ast}:R] = |\text{ker}(\phi)| = 2$, that is:

$|R| = \frac{p-1}{2}$.

This, in effect, let's us choose "positive" elements of a finite field: just as in the case of real numbers, the "positive" elements are the ones that be written as the square of another (non-zero) element of the field. The rules for the cosets $R$ and $-R$ are the same as the rules we learned for positive and negative real numbers under "ordinary" multiplication:

$R\ast R = R$
$R \ast -R = -R \ast R = -R$
$-R \ast -R = R$.

This allows us to use "parity" arguments in some cases, saving time and sometimes considerable calculation.

Great expository post!