# Quadratic Residues

Integers which are perfect squares are rare; only about $\frac1{\sqrt{x}}$ of the integers in the set $\{ 1, 2, \ldots, x \}$ are perfect squares. On the other hand, given an odd prime $p$, integers that are squares modulo $p$ are relatively common. In fact, it turns out that exactly *half* of the integers between $1$ and $p-1$ are squares mod $p$; that is, the congruence $x^2 \equiv a$ mod $p$ has a solution $x$ for exactly half of the values of $a$ in $\{ 1, 2, \ldots, p-1 \}$.

If $a$ and $m$ are coprime integers, then $a$ is called aquadratic residue modulo $m$if the congruence $x^2\equiv a\pmod m$ has a solution.Likewise, if it has no solution, then it is called a

quadratic non-residue modulo $m$.

The natural next question is, "Given $m,$ what are the quadratic residues mod $m ?$" This question and its answer are of great interest in number theory and cryptography.

#### Contents

## An Explicit Example

Find the quadratic residues mod $11$.

When $x = 0$, $x^2 \bmod 11 = 0^2 \bmod 11 = 0$.

When $x = 1$, $x^2 \bmod 11 = 1^2 \bmod 11 = \color{#20A900}1$.

When $x = 2$, $x^2 \bmod 11 = 2^2 \bmod 11 = \color{#3D99F6}4$.

When $x = 3$, $x^2 \bmod 11 = 3^2 \bmod 11 = \color{#EC7300}9$.

When $x = 4$, $x^2 \bmod 11 = 4^2 \bmod 11 = \color{#624F41}5$.

When $x = 5$, $x^2 \bmod 11 = 5^2 \bmod 11 = \color{#318ce7}3$.

When $x = 6$, $x^2 \bmod 11 = 6^2 \bmod 11 = \color{#318ce7}3$.

When $x = 7$, $x^2 \bmod 11 = 7^2 \bmod 11 = \color{#624F41}5$.

When $x = 8$, $x^2 \bmod 11 = 8^2 \bmod 11 = \color{#EC7300}9$.

When $x = 9$, $x^2 \bmod 11 = 9^2 \bmod 11 = \color{#3D99F6}4$.

When $x = 10$, $x^2 \bmod 11 = 10^2 \bmod 11 = \color{#20A900}1$.So the quadratic residues mod $11$ are $1,3,4,5,9$, and the non-residues are $2,6,7,8,10$. $_\square$

Note:A number that is congruent to $0 \bmod p$ is neither a residue nor a non-residue.

## Number of Residues

Notice that the numbers that are colored above are in the order of $\{1,4,9,5,3,3,5,9,4,1\}$. That is,

- the first number and the last number are
**equal**; - the second number and the second last number are
**equal**; - the third number and the third last number are
**equal**, and so on.

This is because $x^2 \equiv (-x)^2 \pmod p$. So the squares of the first half of the nonzero numbers mod $p$ give a complete list of the nonzero quadratic residues mod $p$. In general, we have the following fact:

Fact:If $p$ is an odd prime, the residue classes of $0^2,1^2,2^2,\ldots, \big(\frac{p-1}2\big)^2$ are distinct and give a complete list of the quadratic residues modulo $p$. So there are $\frac{p-1}2$ residues and $\frac{p-1}2$ non-residues (note that we are not counting 0, as mentioned above).

They give a complete list because $x^2$ and $(p-x)^2$ are the same mod $p$ as in the example. To see that they are distinct, note that

$\begin{aligned} x^2 \equiv y^2 \pmod p &\Longleftrightarrow p|x^2-y^2 \\ &\Longleftrightarrow p|(x-y)(x+y) \\ &\Longleftrightarrow p|(x-y) \ \text{or} \ p|(x+y), \end{aligned}$

which is impossible if $x$ and $y$ are two different members of the set $\left\{ 0, 1, 2, \ldots, \frac{p-1}2 \right\}$. $_\square$

## Application to a Famous Theorem

Let $p$ be a prime. Show that the congruence $x^2+y^2+1 \equiv 0$ mod $p$ always has a solution $(x,y)$.

It is clear for $p =2$, so assume $p$ is odd. The above work shows that there are $\frac{p+1}2$ elements of $\{ 0,1,\ldots,p-1 \}$ that can be written as $x^2$ mod $p$, and for the same reason there are $\frac{p+1}2$ elements of $\{0,1,\ldots,p-1 \}$ that can be written as $-1-y^2$ mod $p$. Since the sum of the sizes of these two subsets is $p+1$ and $\{0,1,\ldots,p-1\}$ has $p$ elements, the two subsets must overlap somewhere, i.e.

$x^2 \equiv -1-y^2 \pmod p \Longleftrightarrow x^2+y^2+1 \equiv 0 \pmod p$

for some $x,y$. $_\square$

The above result happens to be a key lemma in the proof of Lagrange's famous *four squares theorem*, which states that every positive integer can be written as a sum of four integer squares. (See the wiki Sum of Squares Theorems.)

## Solving Diophantine Equations

The techniques used to compute quadratic residues mod $p$ are contained in the article on Legendre symbols. This section focuses on general quadratic Diophantine equations, including situations where the modulus is not prime.

For quadratic Diophantine equations, completing the square is often helpful.

Determine whether there exists an integer $x$ such that $37$ divides $x^2 - 31x + 34$.

Modulo 37, we have

$x^2 -31 x + 34 \equiv x^2 + 6x -3 = x^2 + 6x + 9 - 12 = (x+3)^2 - 12.$

So this has a solution if and only if $12$ is a quadratic residue mod $37$. By inspection, $7^2 \equiv 12$ mod $37$, so the equation has solutions; setting $x+3 = 7$ gives $x = 4$ as one of them. $_\square$

For composite modulus, the Chinese remainder theorem is an important tool to break the problem down into prime power moduli.

Determine the number of positive integers $x$ less than 1000 such that when $x^2$ is divided by 840, it leaves a remainder of 60.

Converting it into a congruence, we have $x^2 \equiv 60 \pmod{840}$. Factoring 840 into a product of prime powers gives $840=3\cdot 5\cdot 7\cdot 8$.

So we have $x^2 \equiv 0 \pmod 3,x^2 \equiv 0 \pmod 5,x^2 \equiv 4 \pmod 7,x^2 \equiv 4\pmod 8$.

The first two congruences imply $x^2 \equiv 0$ mod $15$.

Solving the other two congruences shows that $x\equiv \pm \ 2\pmod 7, x \equiv \pm \ 2 \pmod 8$.By the Chinese remainder theorem, $x \equiv 2,26,30,54 \pmod{56}$ and $x \equiv 0 \pmod {15}$.

By the Chinese remainder theorem again, $x \equiv \pm 30, \pm 390 \pmod {840}$.With the restriction of $0 < x < 1000$, there are $5$ solutions in all: $x = 30, 390, 450, 810, 870$. $_\square$

Let

$N= 3 \times 5 \times 7 \times 11 \times 13.$

There are $X$ possibilities for the units digit of a perfect square when it is represented in base $N.$ Compute the last three digits of $X$ (in base 10).

**Details and Assumptions:**

- We are talking about $3, 5, 7, 11, 13$ in their decimal representations.
- You might want to use the fact that $3, 5, 7, 11, 13$ are all primes.

## See Also

**Cite as:**Quadratic Residues.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/quadratic-residues/