Franklin's Notes


Quadratic residues modulo m

A quadratic residue modulo $m$ is an number which is congruent to a perfect square modulo $m$. A quadratic nonresidue modulo $m$ is a number which is not congruent to a perfect square modulo $m$.

Proposition 1. If $p$ is an odd prime, exactly half of the elements of $U_p$ (the units, or nonzero elements, of $\mathbb Z_p$) are quadratic residues. Further, every quadratic residue has precisely $2$ square roots.

Proof. Suppose $a=b^2$ is a quadratic residue modulo $p$, so that the equation $x^2-a=0$ has two solutions. We can factor this polynomial in the form $(x-b)(x+b)$, and because $\mathbb Z_p[x]$ is a field, we have that $\mathbb Z_p[x]$ has a division algorithm and unique factorization, so that this is a unique factorization. Therefore $x^2-a$ has exactly two roots, namely $x=b$ and $x=-b$. Since every QR has exactly two square roots, and there are precisely $p-1$ elements of $U_p$, they can put into pairs where the elements of each pair have the same square, so that there are precisely $\tfrac{p-1}{2}$ distinct quadratic residues. (Notice that $b$ and $-b$ are unequal modulo $p$ because $p$ is odd.) $\blacksquare$

Proposition 2. If $p$ is an odd prime, then $-1$ is a quadratic residue modulo $p$ if and only if $p\equiv 1\bmod 4$.

Proof. Consider the following polynomial in the polynomial ring $\mathbb Z_p[x]$: By Euler's Theorem , the roots of this polynomial are precisely the units in $U_p$. Because $p$ is odd, we may factor this polynomial as follows: Each root of $x^{p-1}-1$, and therefore each unit of $U_p$, must be a root of precisely one of these factors, so that there exists $u\in U_p$ such that $u^{\tfrac{p-1}{2}}+1=0$. But if $p\equiv 1\bmod 4$, then we have that $\tfrac{p-1}{4}$ is an integer, and $u^{\tfrac{p-1}{4}}$ is a unit whose square is equal to $-1$, making $-1$ a QR modulo $p$. Hence, $p\equiv 1\bmod 4$ implies $-1$ is a QR mod $p$.

Now, if $-1$ is a QR modulo an odd prime $p$, then we have that there exists $a,k\in\mathbb Z$ such that $pk=a^2+1$. In $\mathbb Z[i]$, this means that $p|a^2+1=(a+i)(a-i)$. But clearly neither $a+i$ nor $a-i$ can be divisible by the rational prime $p$, hence $p$ must not be prime in $\mathbb Z[i]$, meaning that it must have a factorization in the form $p=(x+yi)(x-yi)$, so that $p=x^2+y^2$. But the only numbers which are sums of two squares are $\equiv 0,1,2\bmod 4$, and since $p$ is odd, we have that $p\equiv 1\bmod 4$, confirming the other direction of implication. $\blacksquare$

number-theory

abstract-algebra

back to home page