Quadratic Congruences and Quadratic Residues

First we discuss transforming and solving quadratic congruence equations. We then study quadratic residues using the Legendre symbol. Euler’s and Gauss’s Criterions are motivated and then the infamous Law of Quadratic Reciprocity is understood.

General Quadratic Congruence

Consider the general quadratic congruence, $$a x^2+b x+c\equiv 0 \pmod{p}$$ where $p$ is an odd prime and $(a,p)=1.$ Inspired by completing the square, we have \begin{equation} \begin{array}{l} a x^2+b x+c\equiv 0 \pmod{p} \\ 4 a^2 x^2+4 a b x+4 a c\equiv 0 \pmod{p} \\ 4a^2x^2+4a b x+4a c+\left(b^2-4a c\right)\equiv \left(b^2- 4 a c\right) \pmod{p} \\ 4a^2x^2+4a b x+b^2\equiv b^2- 4 a c \pmod{p} \\ (2a x+b)^2\equiv b^2- 4 a c \pmod{p} \end{array} \end{equation}

Let $y=2a x+b$ and $d=b^2-4 a c,$ then we have a simplified version, namely \begin{equation} y^2\equiv d \pmod{p}. \label{qcimp} \end{equation} Thus, solving \eqref{qcimp} becomes the impetus.

Quadratic Residues

Definition. Let $m$ be a positive integer with $(a,m)=1.$ If $x^2\equiv a \pmod{m}$ has a solution then $a$ is a quadratic residue of $m.$ If $x^2\equiv a \pmod{m}$ does not have solution then $a$ is a quadratic nonresidue of $m.$

Theorem. Let $p$ be an odd prime. If $(a,p)=1,$ then $x^2\equiv a \pmod{p}$ either has no solutions or exactly two incongruent solutions modulo $p.$

Proof. If $x_0$ is a solution for $x^2\equiv a \pmod{p}$ then so is $-x_0.$ If $x_0\equiv -x_0 \pmod{p}$ then $2x_0\equiv 0 \pmod{p}$ and so $x_0\equiv 0 \pmod{p}$ since $p$ is odd. Clearly, this can not happen and so if there are any solutions there are at least two incongruent solutions. If $x_0$ and $x_1$ are both solutions then $$x_0^2-x_1^2\equiv \left(x_0-x_1\right)\left(x_0+x_1\right)\equiv 0 \pmod{p}$$ and so either $x_0\equiv -x_1 \pmod{p}$ or $x_0\equiv x_1 \pmod{p}.$

The Legendre Symbol

The Legendre symbol is named after the famous mathematician Adrien-Marie Legendre.

Definition. Let $p$ be an odd prime with $(a,p)=1.$ The Legendre symbol is defined as follows: $$\left(\frac{a}{p}\right)=\begin{cases} 1 & \text{if $a$ is a quadratic residue of } p \\ -1 & \text{if $a$ is a quadratic nonresidue of } p\end{cases}$$

Since the quadratic residues of 13 are $1, 3, 4, 9, 10, 12$ and the quadratic non-residues of 13 are $2, 5, 6, 7, 8, 11.$ We can rewrite using the Legendre symbol, \begin{equation} \left(\frac{1}{13}\right) = \left(\frac{3}{13}\right) = \left(\frac{4}{13}\right) = \left(\frac{9}{13}\right) = \left(\frac{10}{13}\right) = \left(\frac{12}{13}\right) = 1 \end{equation} \begin{equation} \left(\frac{2}{13}\right) = \left(\frac{5}{13}\right) = \left(\frac{6}{13}\right) = \left(\frac{7}{13}\right) = \left(\frac{8}{13}\right) = \left(\frac{11}{13}\right) = -1.\end{equation} Notice the relationship the quadratic residues and quadratic non-residues of 13 satisfies: \begin{equation} 1^6 \equiv 3^6\equiv 4^6\equiv 9^6\equiv 10^6\equiv 12^6\equiv 1\pmod{13} \end{equation} and \begin{equation}2^6 \equiv 5^6\equiv 6^6\equiv 7^6\equiv 8^6\equiv 11^6\equiv -1\pmod{13}. \end{equation} So for each of these $a’s$ we have $\left(\frac{a}{13}\right)\equiv a^{(13-1)/2}\text{ }\pmod{13}.$ Also notice that for $p=17,$ \begin{equation} 1^8 \equiv 2^8\equiv 4^8\equiv 8^8\equiv 9^8\equiv 13^8\equiv 15^8\equiv 16^8\equiv 1\pmod{17}\end{equation} and \begin{equation} 3^8 \equiv 5^8\equiv 6^8\equiv 7^8\equiv 10^8\equiv 11^8\equiv 12^8\equiv 14^8\equiv -1\pmod{17}. \end{equation} So again for each of these $a’s$ we have $\left(\frac{a}{17}\right)\equiv a^{(17-1)/2} \pmod{17}.$

Euler’s Criterion for Quadratic Congruences

Leonhard Euler was certainly one of the most prolific and consequential mathematicians of all time.

Theorem. (Euler’s Criterion) Let $p$ be an odd prime and $(a,p)=1.$ Then $$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \pmod{p}.$$

Proof. The only values for $a^{(p-1)/2}$ are $\pm 1$ $\pmod{p}.$ So it suffices to consider the cases $$\left(\frac{a}{p}\right)=1 \quad \text{and}\quad \left(\frac{a}{p}\right)=-1.$$ If $\left(\frac{a}{p}\right)=1$ then $x^2\equiv a \pmod{p}$ has a solution say $x_0.$ Then by Fermat’s Little theorem, $$a^{(p-1)/2} \equiv \left(x_0^2\right)^{(p-1)/2} \equiv x_0^{p-1} \equiv 1 \pmod{p}$$ since $\left(x_0,p\right)=1.$ Conversely, if $\left(\frac{a}{p}\right)=-1$ then $x^2\equiv a \pmod{p}$ has no solution. The key idea is that we can group together the integers $1, 2, 3, \ldots, p-1$ into $(p-1)/2$ pairs each with product of $a.$ Then multiplying these pairs together, and using Wilson’s theorem, we have $$ a^{(p-1)/2}\equiv (p-1)!\equiv -1=\left(\frac{a}{p}\right) \pmod{p}.$$ To see why we can do this, note that $(y,p)=1$ means $y x\equiv a \pmod{p}$ has exactly one solution say $x$ and this must happen precisely when $x\neq y.$

Example. Use Euler’s Criterion to determine $\left(\frac{5}{23}\right)$ and $\left(\frac{9}{53}\right).$

Solution. Since $(5,23)=1$ we have, by Euler’s criterion, $$\left(\frac{5}{23}\right)\equiv 5^{11}\equiv 22\equiv -1 \pmod{23}$$ and so $5$ is a quadratic nonresidue of 23. Similarly, $$\left(\frac{9}{53}\right)\equiv 9^{26}\equiv 1 \pmod{53}$$ and so $9$ is a quadratic residue of 53.

Gauss’s Criterion for Quadratic Congruences

Johann Carl Friedrich Gauss was certainly one of the most ingenious and influential mathematicians of all time.

Theorem. (Gauss’s Criterion) Let $p$ be an odd prime with $(a,p)=1.$ If $n$ is the number of least positive residues of the integers $a, 2a, 3a, \ldots, ((p-1)/2)a$ that exceed $p/2,$ then $\left(\frac{a}{p}\right)=(-1)^n.$

Proof. Let $$ A=\left\{a, 2a, 3a, \ldots, \left(\frac{p-1}{2}\right)a\right\}$$ and $\left\{r_1,r_2, \ldots, r_n\right\}$ be those least positive residues of $A$ that exceed $p/2$, and $\left\{s_1,s_2, \ldots, s_m\right\}$ be those least positive residues of $A$ that do not exceed $p/2.$ It follows that $$ \left\{p-r_1,p-r_2, \ldots ,p-r_n,s_1,s_2, \ldots ,s_m\right\}$$ is a permutation of the set $\left\{1,2,3, \ldots,\left(\frac{p-1}{2}\right)\right\}$, and so $$\left(p-r_1\right)\left(p-r_2\right)\cdot \cdot \cdot \left(p-r_n\right)s_1s_2\cdot \cdot \cdot s_m=1\cdot 2\cdot 3\cdot \cdot \cdot \left(\frac{p-1}{2}\right).$$ Simplifying with modulus $p,$ we have $$(-1)^nr_1r_2\cdot \cdot \cdot r_ns_1s_2\cdot \cdot \cdot s_m\equiv \left(\frac{p-1}{2}\right)! \pmod{p}$$ By definition of the $r_i’s$ and $s_i’s$ we know, $$(-1)^na(2a)(3a)\cdot \cdot \cdot \left(\frac{p-1}{2}\right)a\equiv \left(\frac{p-1}{2}\right) \pmod{p}$$ $$(-1)^na^{(p-1)/2}\left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)! %\pmod{p} (-1)^na^{(p-1)/2} \equiv 1 \pmod{p}.$$ By Euler’s Criterion $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\equiv (-1)^n \pmod{p}$ as desired.

Example. Find $\left(\frac{7}{13}\right)$ and $\left(\frac{9}{53}\right)$ using Gauss’s Lemma.

Solution. Since $(13-1)/2=6$ we look at the first 6 multiples of 7 namely: $7, 14, 21, 28, 35, 42.$ The least positive residues $\pmod{13}$ are $7, 1, 8, 2, 9, 3 .$ The number of them that exceed $13/2$ is 3 namely: $7, 8, 9.$ Therefore, $$\left(\frac{7}{13}\right)=(-1)^3=-1.$$ Since $(53-1)/2=26$ we look at the first 26 multiples of 9 (mod 53) namely $$ \begin{array}{ccccccccccccc} 9 & 18 & 27 & 36 & 45 & 1 & 10 & 19 & 28 & 37 & 46 & 2 & 11 \\ 20 & 29 & 38 & 47 & 3 & 12 & 21 & 30 & 39 & 48 & 4 & 13 & 22. \end{array} $$ The number of them that exceeds $53/2$ is 12. Therefore, $$\left(\frac{9}{53}\right)=(-1)^{12}=1$$ as desired.

Quadratic Characters

Example. (Quadratic Characters) Show that if $p$ is an odd prime, then \begin{equation} \left(\frac{-1}{p}\right)=\begin{cases}1 & p\equiv 1 \pmod{4} \ -1 & p\equiv 3 \pmod{4}. \end{cases} \end{equation} \begin{equation} \left(\frac{2}{p}\right)=\begin{cases} 1 & p\equiv 1 \text{ or } 7\pmod{8}\ -1 & p\equiv 3 \text{ or } 5 \pmod{8}. \end{cases} \end{equation} \begin{equation} \left(\frac{3}{p}\right)=\begin{cases}1 & p\equiv 1 \text{ or } 11 \pmod{12} \ -1 & p\equiv 5 \text{ or } 7 \pmod{12}. \end{cases} \end{equation}

Solution. To verify the first, notice every odd prime is of the form $p=4k+1$ (that is $p\equiv 1 \pmod{4}$) or of the form $p=4k+3$ (that is $p\equiv -1 \pmod{4}$). In the first case, Euler’s Criterion yields $$1\equiv (-1)^{(p-1)/2}\equiv \left(\frac{-1}{p}\right)$$ because $(p-1)/2$ is even. In the latter case, $(p-1)/2$ is odd and so Euler’s Criterion yields $$-1\equiv (-1)^{(p-1)/2}\equiv \left(\frac{-1}{p}\right).$$ The reader should verify the remaining formulas.

Properties of the Legendre Symbol

Lemma. Let $p$ be an odd prime with $(a,p)=(b,p)=1.$ If $a\equiv b \pmod{p}$ then $$ \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$$

Proof. The congruence $x^2\equiv a$ has a solution if and only if $x^2\equiv b \pmod{p}$ does because $a\equiv b \pmod{p}.$

Lemma. If $p$ is an odd prime with $(a,p)=(b,p)=1$, then \begin{equation} \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) =\left(\frac{a b}{p}\right). \end{equation}

Proof. By Euler’s Criterion we know $$ a^{(p-1)/2}\equiv \left(\frac{a}{p}\right), \hspace{.5cm} b^{(p-1)/2}\equiv \left(\frac{b}{p}\right), \hspace{.5cm} \text{ and } \hspace{.5cm} (a b)^{(p-1)/2}\equiv \left(\frac{a b}{p}\right).$$ Therefore, $$\left(\frac{a b}{p}\right)\equiv (a b)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \pmod{p}$$ and because the only values possible are $\pm 1$.

Lemma. If $p$ is an odd prime with $(a,p)=1$, then $\left(\frac{a^2}{p}\right)=1.$

Proof. From above we have $$ \left(\frac{a^2}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{a}{p}\right)=1$$ as desired.

Lemma. If $p$ is an odd prime with $(a,p)=(b,p)=1$, then $$\left(\frac{a b^2}{p}\right)=\left(\frac{a}{p}\right). $$

Proof. From above we have $$ \left(\frac{a b^2}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b^2}{p}\right)=\left(\frac{a}{p}\right)$$ follows immediately.

Theorem. If $n$ has prime factorization $$n=p_1{}^{2t_1+1}\cdot \cdot \cdot p_k{}^{2t_k+1}p_{k+1}^{2t_{k+1}} \cdots p_m^{2t_m}$$ and $q$ is a prime not dividing $n$, then $$ \left(\frac{n}{q}\right)=\left(\frac{p_1}{q} \right)\left(\frac{p_2}{q}\right)\cdot \cdot \cdot \left(\frac{p_k}{q}\right).$$

Proof. From above we have $$\left(\frac{n}{q}\right) = \left(\frac{p_1^{2t_1+1}}{q}\right)\left(\frac{p_2^{2t_2+1}}{q}\right)\cdots \left(\frac{p_k^{2t_k+1}}{q}\right)\left(\frac{p_{k+1}^{2t_k}}{q}\right)\cdots \left(\frac{p_m^{2t_m}}{q}\right) $$ Therefore, we see that $ \left(\frac{n}{q}\right)=\left(\frac{p_1}{q}\right)\left(\frac{p_2}{q}\right)\cdots \left(\frac{p_k}{q}\right)$ as desired.

Law of Quadratic Reciprocity

The Law of Quadratic Reciprocity is one of the most celebrated theorems in mathematics and in indispensable for solving quadratic congruences.

Theorem. (Law of Quadratic Reciprocity) Let $p$ and $q$ be distinct odd primes, then $$ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{(p-1)/2(q-1)/2}.$$

Notice that the Law of Quadratic Reciprocity is equivalent to the following. \begin{equation}\left(\frac{p}{q}\right) = \left\{ \begin{array}{cl} -\left(\frac{q}{p}\right) & \text{ if } p\equiv q\equiv 3 \pmod{4} \\ \left(\frac{q}{p}\right) & \text{ otherwise } \end{array}\right. \end{equation}

Example. Evaluate $\left(\frac{29}{53}\right).$

Solution. Since $29\equiv 1 \pmod{4}$ we have $\left(\frac{29}{53}\right)=\left(\frac{53}{29}\right).$ Since $53\equiv 24 \pmod{29}$ and $24=2^26$, \begin{align} \left(\frac{29}{53}\right) & =\left(\frac{24}{29}\right) =\left(\frac{6}{29}\right) =\left(\frac{2}{29}\right)\left(\frac{3}{29}\right) \\ & =(-1)\left(\frac{3}{29}\right) =(-1)\left(\frac{29}{3}\right) =(-1)\left(\frac{2}{3}\right) =1. \end{align} which shows $x^2\equiv 29 \pmod{53}$ is not solvable.

Example. Evaluate $\left(\frac{30}{43}\right).$

Solution. To evaluate $\left(\frac{30}{43}\right)$ we note that $30=2\cdot 3\cdot 5.$ So we have $$\left(\frac{30}{43}\right) = \left(\frac{2}{43}\right)\left(\frac{3}{43}\right)\left(\frac{5}{43}\right) $$ and since $43\equiv 3 \pmod{4},$ we see that $$\left(\frac{30}{43}\right) =\left(\frac{2}{43}\right)(-1)\left(\frac{43}{3}\right)\left(\frac{43}{5}\right).$$ Finally since $43\equiv 3 \pmod{8},$ $43\equiv 1 \pmod{3},$ and $43\equiv 3 \pmod{5}$ and so \begin{align} \left(\frac{30}{43}\right) = (-1)\left(\frac{1}{3}\right) \left(\frac{3}{5}\right) =(-1)\left(\frac{3}{5}\right) = (-1)\left(\frac{5}{3}\right) =(-1)\left(\frac{2}{3}\right) =-1 \end{align} which shows $x^2\equiv 30 \pmod{43}$ is not solvable.

Using the Law of Quadratic Reciprocity

Example. Evaluate $\left(\frac{713}{1009}\right).$

Solution. Since $713=23\cdot 31$ we have $$\left(\frac{713}{1009}\right)=\left(\frac{23}{1009}\right)\left(\frac{31}{1009}\right).$$ So we break these down into the two parts 23 and 31 as follows: \begin{align*} & \left(\frac{23}{1009}\right) =\left(\frac{1009}{23}\right) & \text{ since } 1009\equiv 1 \pmod{4} \\ & \left(\frac{1009}{23}\right) =\left(\frac{20}{23}\right) & \text{ since } 1009\equiv 20 \pmod{23} \\ & \left(\frac{20}{23}\right) =\left(\frac{5}{23}\right) & \text{ since } 20=4^2\cdot 5 \\ & \left(\frac{5}{23}\right)=\left(\frac{23}{5}\right) & \text{ since } 5\equiv 1 \pmod{4} \\ & \left(\frac{23}{5}\right) =\left(\frac{3}{5}\right) & \text{ since } 23\equiv 3 \pmod{5} \\ & \left(\frac{3}{5}\right) =\left(\frac{5}{3}\right) & \text{ since } 5\equiv 1 \pmod{4} \\ & \left(\frac{5}{3}\right) =\left(\frac{2}{3}\right) & \text{ since } 5\equiv 2 \pmod{3}\\ & \left(\frac{2}{3}\right)=-1 & \text{ since } 3\equiv 3 \pmod{8} \end{align*}

and the second part follows from, \begin{align*} & \left(\frac{31}{1009} \right) =\left(\frac{1009}{31}\right) & \text{ since } 1009\equiv 1 \pmod{4}\\ & \left(\frac{1009}{31}\right) = \left(\frac{17}{31}\right) & \text{ since } 1009 \equiv 17 \pmod{31}\\ & \left(\frac{17}{31}\right) = \left(\frac{31}{17}\right) & \text{ since } 17\equiv 1 \pmod{4}\\ & \left(\frac{31}{17}\right) = \left(\frac{14}{17}\right) & \text{ since } 31\equiv 14 \pmod{17}\\ & \left(\frac{14}{17}\right) = \left(\frac{2}{17}\right) \left(\frac{7}{17}\right) & \text{ since } 14=2\cdot 7\\ & \left(\frac{2}{17}\right)\left(\frac{7}{17}\right) =\left(\frac{7}{17}\right) & \text{ since } 17\equiv 1 \pmod{8}\\ & \left(\frac{7}{17}\right) = \left(\frac{17}{7}\right) & \text{ since } 17\equiv 1 \pmod{4}\\ & \left(\frac{17}{7}\right) = \left(\frac{3}{7}\right) & \text{ since } 17\equiv 3 \pmod{7}\\ & \left(\frac{3}{7}\right) = (-1)\left(\frac{7}{3}\right) & \text{ since } 7\equiv 3 \pmod{4} \text{ and } 3\equiv 3 \pmod{4}\\ & (-1)\left(\frac{7}{3}\right) = (-1)\left(\frac{1}{3}\right)=-1 & \text{ since } 7\equiv 1 \pmod{3}. \end{align*}

\begin{align*} & \left(\frac{31}{1009}\right) =\left(\frac{1009}{31}\right) & \text{ since } 1009\equiv 1 \pmod{4} \\ & \left(\frac{1009}{31}\right)=\left(\frac{17}{31}\right) & \text{ since } 1009\equiv 17 \pmod{31} \\ & \left(\frac{17}{31} \right) =\left(\frac{31}{17}\right) & \text{ since } 17\equiv 1 \pmod{4} \\ & \left(\frac{31}{17}\right)=\left(\frac{14}{17}\right) & \text{ since } 31\equiv 14 \pmod{17} \\ & \left(\frac{14}{17}\right)=\left(\frac{2}{17}\right) \left(\frac{7}{17}\right) & \text{ since } 14=2\cdot 7 \\ & \left(\frac{2}{17}\right)\left(\frac{7}{17}\right)=\left(\frac{7}{17}\right) & \text{ since } 17\equiv 1 \pmod{8} \\ & \left(\frac{7}{17}\right)=\left(\frac{17}{7}\right) & \text{ since } 17\equiv 1 \pmod{4} \\ & \left(\frac{17}{7}\right)=\left(\frac{3}{7}\right) & \text{ since } 17\equiv 3 \pmod{7} \\ & \left(\frac{3}{7}\right)=(-1)\left(\frac{7}{3}\right) & \text{ since } 7\equiv 3 \pmod{4} \text{ and } 3\equiv 3 \pmod{4} \\ & (-1)\left(\frac{7}{3}\right)=(-1)\left(\frac{1}{3}\right)=-1 & \text{ since } 7\equiv 1 \pmod{3}. \end{align*}

Therefore, $\left(\frac{713}{1009}\right)=1.$

Solve a Quadratic Congruence

Example. Solve the quadratic congruence $5x^2-3x+21\equiv 0 \pmod{53}.$

Solution. Let $y=2a x+b=10x-3$ and $d=(-3)^2-4(5 (21)=-411\equiv 13 \pmod{53}.$ So the congruence becomes $y^2\equiv 13 \pmod{53}.$ We find that $y\equiv 15 \pmod{53}$ and $y\equiv 38 \pmod{53}$. Therefore we solve, $10x-3\equiv 15 \pmod{53}$ and $10x-3\equiv 38 \pmod{53}.$ We find $x\equiv 23 \pmod{53}$ and $x\equiv 20 \pmod{53}.$

Exercises on Quadratic Congruences

Exercise. Find a congruence describing all primes for which 5 is a quadratic residue.

Exercise. Find a congruence describing all primes for which 7 is a quadratic residue.

Exercise. Evaluate the Legendre symbol.

$(1) \quad \left(\frac{7}{79}\right)$

$(2) \quad \left(\frac{15}{101}\right)$

$(3) \quad \left(\frac{31}{641}\right)$

$(4) \quad \left(\frac{111}{991}\right)$

$(5) \quad \left(\frac{105}{1009}\right)$

$(6) \quad \left(\frac{1005}{10009}\right)$

Exercise. Solve the quadratic congruence.

$(1) \quad x^2+x+1\equiv 0 \pmod{7}$

$(2) \quad x^2+5x+1\equiv 0 \pmod{7}$

$(3) \quad x^2+3x+1\equiv 0 \pmod{7}$

$(4) \quad x^2\equiv 1 \pmod{15}$

$(5) \quad x^2\equiv 58 \pmod{77}$

$(6) \quad x^2\equiv 207 \pmod{1001}$

Exercise. Evaluate the Legendre symbols $\left( \frac{221}{881} \right)$ and $\left( \frac{855}{1009} \right).$

Exercise. Determine which of the following quadratic congruences has solutions

$(1) \quad 16x^2+5x+1\equiv 0 \pmod{31}$

$(2) \quad 16x^2-5x+1\equiv 0 \pmod{101}$

Exercise. Let $p$ be an odd prime. Show that the quadratic congruence equation $a x^2+bx +c\equiv 0 \pmod{p}$ has a solution if and only if $$\left(\frac{b^2-4ac}{p}\right)=1.$$

Exercise. Solve $2 x^2 – 17 x + 1\equiv 0 \pmod{111400}.$

Exercise. Let $a$ and $b$ be integers not divisible by the prime $p.$ Show that either one or all three of the integers $a, b,$ and $a b$ are quadratic residues of $p.$

More Exercises on Quadratic Congruences

Exercise. Using the law of quadratic reciprocity to show each of the following is true.

$(1) \quad \left(\frac{3}{p}\right)=\begin{cases}1 & p\equiv \pm 1 \pmod{12} \\ -1 & p\equiv \pm 5\pmod{12} \end{cases} $

$(2) \quad \left(\frac{-3}{p}\right)=\begin{cases}1 & p\equiv 1 \pmod{6} \\ -1 & p\equiv -1 \pmod{6} \end{cases}$

Exercise. Find all of the quadratic residues of the following integers.

$(1) \quad 7$

$(2) \quad 8$

$(3) \quad 15$

$(4) \quad 18$

Exercise. Find the value of the Legendre symbol $\left(\frac{j}{11}\right)$ for $j=1,2,3,4,5,$ and 6.

Exercise. Evaluate the Legendre symbol $\left(\frac{7}{11}\right)$ using Euler’s criterion.

Exercise. Evaluate the Legendre symbol $\left(\frac{7}{11}\right)$ using Gauss’s lemma.

Exercise. Let $a$ and $b$ be integers not divisible by the prime $p.$ Show that either one or all three of the integers $a, b,$ and $a b$ are quadratic residues of $p.$

Exercise. (a) Find a congruence describing all primes for which 5 is a quadratic residue. (b) Find a congruence describing all primes for which 7 is a quadratic residue.

Exercise. Find all the quadratic residues of $13.$

Exercise. Determine if $x^2\equiv 105 \pmod{1009}$ is solvable using Legendre symbols.

Exercise. Use Hensel’s lifting theorem and the Chinese Remainder Theorem to solve the quadratic congruence equation $3x^2+11x+2\equiv 0 \pmod{72}.$

Related Articles

Follow Me
Latest posts by David A. Smith (see all)