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!

 

[CellCoree]

I would like to introduce quadratic residues as a fundamental concept in number theory that has numerous real world applications. One of the most motivating ways to introduce quadratic residues is by highlighting their connection to the Law of Quadratic Reciprocity.

The Law of Quadratic Reciprocity is a fundamental theorem in number theory that relates the quadratic residues of two different prime numbers. It states that the quadratic residue of a prime number p, modulo another prime number q, is equal to the quadratic residue of q, modulo p, if and only if p and q are congruent to each other modulo 4. This law has been proven to be true for all prime numbers and has many real world applications.

One real life example of quadratic residues can be seen in cryptography. The RSA encryption algorithm, which is widely used for secure communication over the internet, relies on the difficulty of finding quadratic residues modulo a large composite number. This application highlights the importance of quadratic residues in ensuring the security of sensitive information.

Another example can be found in coding theory, where quadratic residues are used in constructing error-correcting codes. These codes are essential in the transmission and storage of digital data, making quadratic residues crucial in modern communication systems.

The Law of Quadratic Reciprocity is considered one of the most important theorems in number theory because of its wide range of applications and its significance in other mathematical fields. It has been used in the proofs of many other theorems and has been described as the "master key" to unlocking the secrets of number theory.

In conclusion, quadratic residues and the Law of Quadratic Reciprocity have both theoretical and practical importance in the world of mathematics and beyond. By understanding their applications and significance, we can appreciate the beauty and power of this fundamental concept.