📂Number Theory

Quadratic Residues and Non-Quadratic Residues

Definition ¹

For primes $p \ne 2$ and $a < p$, if there exists a solution to the congruence equation $x^{2} \equiv a \pmod{p}$, then $a$ is called a Quadratic Residue QR modulo $p$. If $a$ is not a quadratic residue, it is called a Non-Quadratic Residue NR.

Explanation

Simply put, a quadratic residue is a number for which a square root exists in $\pmod{p}$.

For example, consider the prime $7$ $$ 1^2 \equiv 1 \pmod{7} \\ 2^2 \equiv 4 \pmod{7} \\ 3^2 \equiv 2 \pmod{7} \\ 4^2 \equiv 2 \pmod{7} \\ 5^2 \equiv 4 \pmod{7} \\ 6^2 \equiv 1 \pmod{7} $$ $1,2,4$ is a QR and $3,5,6$ is an NR. Considering the prime $11$ $$ 1^2 \equiv 1 \pmod{11} \\ 2^2 \equiv 4 \pmod{11} \\ 3^2 \equiv 9 \pmod{11} \\ 4^2 \equiv 5 \pmod{11} \\ 5^2 \equiv 3 \pmod{11} \\ 6^2 \equiv 3 \pmod{11} \\ 7^2 \equiv 5 \pmod{11} \\ 8^2 \equiv 9 \pmod{11} \\ 9^2 \equiv 4 \pmod{11} \\ 10^2 \equiv 1 \pmod{11} $$ $1,3,4,5,9$ is a QR and the rest $2,6,7,8,10$ are NR. Interestingly, QRs appear symmetrically, which is natural because $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ Also, there are always exactly the same number of QRs and NRs.

Theorem

For primes larger than $2$, $p$, there are exactly $\displaystyle {(p-1) \over 2}$ QRs and NRs.

Proof

The list of all numbers squared from $1$ to $p-1$ is as follows. $$ 1^2, 2^2, \cdots , (p-1)^2 $$ However, as we’ve seen $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ so whether we look at $1$ or $p-1$, it’s the same, and whether we look at $2$ or $p-2$, it’s the same. Therefore, it is sufficient to only look at half of the original number $$ 1^2, 2^2, \cdots , \left( {{ p-1 } \over { 2 }} \right)^2 $$ These numbers are all QRs by the definition of QRs, so if we can show that all these numbers are different, then we can say that there are exactly $\displaystyle {(p-1) \over 2}$ QRs. Similarly, since a natural number smaller than $p$ in $\pmod{p}$ is either a QR or an NR, if there are exactly $\displaystyle {(p-1) \over 2}$ QRs, then there must also be exactly $\displaystyle {(p-1) \over 2}$ NRs. The formal proof uses reductio ad absurdum. Let $b_1$ and $b_2$ be two different natural numbers smaller than $\displaystyle {{(p-1)} \over {2}}$.

Assuming ${b_1}^2 \equiv {b_2}^2 \pmod{p}$ holds, then $$ {b_1}^2 - {b_2}^2 \equiv 0 \pmod{p} $$ Therefore, for some integer $k$, ${b_1}^2 - {b_2}^2 = pk$, and the prime $p$ is a divisor of $({b_1} + {b_2})({b_1} - {b_2})$. However, since $b_1$ and $b_2$ are assumed to be smaller than $\displaystyle {{(p-1)} \over {2}}$, $({b_1} + {b_2})$ is smaller than $(p-1)$. Hence, $p$ cannot be a divisor of $({b_1} + {b_2})$, and must therefore be a divisor of $({b_1} - {b_2})$. However, by the same reasoning $|{b_1} - {b_2}|$ is smaller than $(p-1)$, so it must be $0$ to be divided by $p$. That means, ${b_1} = {b_2}$, but we assumed $b_1$ and $b_2$ to be two different natural numbers smaller than $\displaystyle {{(p-1)} \over {2}}$, so this is a contradiction. Therefore, ${b_1}^2 \neq {b_2}^2 \pmod{p}$ and there are exactly $\displaystyle {(p-1) \over 2}$ QRs.

■