📂Number Theory

Quadratic Residues and Non-Quadratic Residues

Definition ¹

For a prime $p \ne 2$ and $a < p$, if the congruence equation $x^{2} \equiv a \pmod{p}$ has a solution, 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 that has a square root in $\pmod{p}$.

For example, considering 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$ are QRs and $3,5,6$ are NRs. 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$ are QRs and the rest, $2,6,7,8,10$, are NRs. Interestingly, the QRs appear symmetrically, which is in fact obvious since $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ Moreover, QRs and NRs always appear in exactly the same number.

Theorem

For a prime $p$ greater than $2$, there exist exactly $\displaystyle {(p-1) \over 2}$ QRs and NRs.

Proof

The list of squares of all numbers from $1$ to $p-1$ is as follows. $$ 1^2, 2^2, \cdots , (p-1)^2 $$ However, as we saw earlier, $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ so looking at $1$ is the same as looking at $p-1$, and looking at $2$ is the same as looking at $p-2$. Therefore, it suffices for us to examine only half of the original list, $$ 1^2, 2^2, \cdots , \left( {{ p-1 } \over { 2 }} \right)^2 $$ These numbers are all QRs by the definition of QR, so if we show that they are all distinct, we can say that there exist exactly $\displaystyle {(p-1) \over 2}$ QRs. Likewise, since in $\pmod{p}$ every natural number less than $p$ is either a QR or an NR, if there exist exactly $\displaystyle {(p-1) \over 2}$ QRs, then there will also exist exactly $\displaystyle {(p-1) \over 2}$ NRs. The main proof uses proof by contradiction. Let $b_1$ and $b_2$ be two distinct natural numbers less than $\displaystyle {{(p-1)} \over {2}}$.

If we assume that ${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 we said $b_1$ and $b_2$ are less than $\displaystyle {{(p-1)} \over {2}}$, $({b_1} + {b_2})$ is less than $(p-1)$. Since $p$ cannot be a divisor of $({b_1} + {b_2})$, it must be a divisor of $({b_1} - {b_2})$. However, for the same reason, $|{b_1} - {b_2}|$ is less than $(p-1)$, so it can only be divisible by $p$ if it is $0$. That is, ${b_1} = {b_2}$, but since $b_1$ and $b_2$ were assumed to be two distinct natural numbers less than $\displaystyle {{(p-1)} \over {2}}$, this is a contradiction. Therefore, ${b_1}^2 \neq {b_2}^2 \pmod{p}$, and there exist exactly $\displaystyle {(p-1) \over 2}$ QRs.

■