Welcome to our community

Be a part of something great, join today!

Number Theory Quadratic Residues

matqkks

Member
Jun 26, 2012
74
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

Well-known member
MHB Math Helper
Mar 22, 2013
573
(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.
 
Last edited:

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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, lets 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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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, lets 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!