A first surprise in elementary number theory is that solving a quadratic congruence is not just a matter of divisibility. The congruence $x^2 \equiv 1 \pmod{p}$ always has the two familiar solutions $x \equiv \pm 1 \pmod{p}$ when $p$ is an odd prime, but the congruence $x^2 \equiv 2 \pmod{p}$ changes its behaviour as $p$ changes. It is soluble modulo $7$, since $3^2 \equiv 2 \pmod{7}$, and insoluble modulo $5$, since the non-zero squares modulo $5$ are only $1$ and $4$. Quadratic residues isolate exactly this phenomenon: which non-zero residue classes modulo an odd prime are squares? The question matters because quadratic congruences are the first place where arithmetic modulo primes develops a visible internal geometry. The non-zero residue classes modulo $p$ form a finite multiplicative group, and the square map folds that group in half. [Quadratic reciprocity](/theorems/1721), primality tests, finite fields, and elementary cryptography all begin with understanding that fold. [example: The First Failure of Naive Square Roots] Let $p=11$. To find the non-zero square classes modulo $11$, it is enough to square the representatives $1,2,3,4,5,6,7,8,9,10$ and reduce each result modulo $11$. The first five give \begin{align*} 1^2 = 1 \equiv 1 \pmod{11}. \end{align*} \begin{align*} 2^2 = 4 \equiv 4 \pmod{11}. \end{align*} \begin{align*} 3^2 = 9 \equiv 9 \pmod{11}. \end{align*} \begin{align*} 4^2 = 16 = 11+5 \equiv 5 \pmod{11}. \end{align*} \begin{align*} 5^2 = 25 = 2\cdot 11+3 \equiv 3 \pmod{11}. \end{align*} The remaining non-zero classes repeat these values because each is the negative of one of the first five classes modulo $11$, and $(-x)^2=x^2$. Explicitly, \begin{align*} 6 \equiv -5 \pmod{11}, \quad 6^2 \equiv (-5)^2 = 25 \equiv 3 \pmod{11}. \end{align*} \begin{align*} 7 \equiv -4 \pmod{11}, \quad 7^2 \equiv (-4)^2 = 16 \equiv 5 \pmod{11}. \end{align*} \begin{align*} 8 \equiv -3 \pmod{11}, \quad 8^2 \equiv (-3)^2 = 9 \pmod{11}. \end{align*} \begin{align*} 9 \equiv -2 \pmod{11}, \quad 9^2 \equiv (-2)^2 = 4 \pmod{11}. \end{align*} \begin{align*} 10 \equiv -1 \pmod{11}, \quad 10^2 \equiv (-1)^2 = 1 \pmod{11}. \end{align*} Therefore the non-zero squares modulo $11$ are exactly $1,3,4,5,9$. The remaining non-zero classes $2,6,7,8,10$ are not squares modulo $11$, so the phrase "take a square root modulo $p$" hides a genuine existence question. [/example] The computation also shows the basic symmetry: $x$ and $-x$ have the same square, and no other duplication occurs among non-zero classes modulo a prime. The theory of quadratic residues turns this symmetry into a test, then into a reciprocity law comparing primes. ## Definition The main definition is designed to record solvability of one very specific congruence. We restrict to odd primes because modulo $2$ the distinction collapses, and we require $p \nmid a$ when speaking of residue versus non-residue so that the zero class does not obscure the multiplicative structure. [definition: Quadratic Residue] Let $p$ be an odd prime and let $a \in \mathbb{Z}$ with $p \nmid a$. The integer $a$ is a quadratic residue modulo $p$ if there exists $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod{p}. \end{align*} The integer $a$ is a quadratic non-residue modulo $p$ if no such $x \in \mathbb{Z}$ exists. [/definition] The definition depends only on the residue class of $a$ modulo $p$. If $a \equiv b \pmod{p}$ and $p \nmid a$, then the congruences $x^2 \equiv a \pmod{p}$ and $x^2 \equiv b \pmod{p}$ have the same solutions modulo $p$. For this reason we often speak about a non-zero class in $\mathbb{Z}/p\mathbb{Z}$ being a square. The next notation packages the yes-or-no answer into a multiplicative symbol. It is useful because products of residues behave predictably, and the symbol turns that behaviour into ordinary multiplication of signs. [definition: Legendre Symbol] Let $p$ be an odd prime. The Legendre symbol modulo $p$ is the function \begin{align*} \left(\frac{\cdot}{p}\right): \mathbb{Z} \to \{-1,0,1\}. \end{align*} Its input-to-output rule is: for $a \in \mathbb{Z}$, the value $\left(\frac{a}{p}\right)$ is $0$ if $p \mid a$, is $1$ if $p \nmid a$ and $a$ is a quadratic residue modulo $p$, and is $-1$ if $p \nmid a$ and $a$ is a quadratic non-residue modulo $p$. [/definition] The value $0$ is included for arithmetic convenience; the residue/non-residue distinction itself concerns the non-zero classes. With this convention the Legendre symbol is defined for every integer $a$, while the phrase quadratic residue still means a non-zero square class unless the zero class is explicitly mentioned. The integer definition is perfect for congruence equations, but it hides the algebraic object doing the work. Passing to residue classes lets us see the square classes as the image of a specific self-map of the unit group. [definition: Square Map Modulo $p$] Let $p$ be an odd prime. The square map modulo $p$ is the function \begin{align*} s_p: (\mathbb{Z}/p\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times. \end{align*} For each $\bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times$, its value is \begin{align*} s_p(\bar{x}) = \bar{x}^2. \end{align*} [/definition] This map is a [group homomorphism](/page/Group%20Homomorphism) because multiplication in the unit group respects squaring. Naming its domain and codomain matters: we are not squaring arbitrary integers, but squaring invertible residue classes and staying inside the same finite group. Once the map is visible, the original solvability question becomes an image-membership question: given a non-zero class $\bar{a}$, is $\bar{a}$ hit by $s_p$? The next definition names exactly those classes, so later counting and subgroup arguments can refer to the image rather than repeatedly unpacking the congruence $x^2 \equiv a \pmod{p}$. [definition: Square Class Modulo $p$] Let $p$ be an odd prime. A square class in $(\mathbb{Z}/p\mathbb{Z})^\times$ is an element $\bar{a} \in (\mathbb{Z}/p\mathbb{Z})^\times$ for which there exists $\bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times$ satisfying \begin{align*} \bar{x}^2 = \bar{a}. \end{align*} [/definition] This is the same notion as a quadratic residue, expressed in the multiplicative group. The advantage is that the square map is now a group homomorphism, so counting and multiplicativity become consequences of group structure. ## The Square Map Modulo a Prime ### Counting Square Classes The first structural question is how many residues there are. The example modulo $11$ suggested half of the non-zero classes are squares. That is not a coincidence; it follows from the fact that $x$ and $-x$ are the only non-zero roots of the same square congruence modulo a prime. [quotetheorem:1714] This theorem gives the first useful mental picture: the square classes form exactly half of $(\mathbb{Z}/p\mathbb{Z})^\times$. To use that half in later arguments, we need to name it as a subset with its own algebraic structure. ### The Residue Subgroup When a construction appears repeatedly, it is worth naming the set it produces. The quadratic residues are not just a list; they form the image of a homomorphism from the unit group to itself. [definition: Quadratic Residue Subgroup] Let $p$ be an odd prime. The quadratic residue subgroup modulo $p$ is \begin{align*} Q_p = \{\bar{x}^2 : \bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times\} \subset (\mathbb{Z}/p\mathbb{Z})^\times. \end{align*} [/definition] The notation $Q_p$ is local to this page: it abbreviates the subgroup of non-zero square classes modulo $p$. Since computations with residues often multiply congruence classes, the next structural fact explains why products of square classes remain controlled. [quotetheorem:9932] The subgroup language explains a common multiplication table: residue times residue gives residue, residue times non-residue gives non-residue, and non-residue times non-residue gives residue. This is the same rule as multiplying signs after applying the Legendre symbol. [example: Multiplication Table Modulo $13$] Modulo $13$, it is enough to square one representative from each pair $\bar{x},-\bar{x}$, because $(-x)^2=x^2$. The first six non-zero classes give \begin{align*} 1^2 = 1 \equiv 1 \pmod{13}. \end{align*} \begin{align*} 2^2 = 4 \equiv 4 \pmod{13}. \end{align*} \begin{align*} 3^2 = 9 \equiv 9 \pmod{13}. \end{align*} \begin{align*} 4^2 = 16 = 13+3 \equiv 3 \pmod{13}. \end{align*} \begin{align*} 5^2 = 25 = 13+12 \equiv 12 \pmod{13}. \end{align*} \begin{align*} 6^2 = 36 = 2\cdot 13+10 \equiv 10 \pmod{13}. \end{align*} Therefore \begin{align*} Q_{13} = \{\bar{1},\bar{3},\bar{4},\bar{9},\bar{10},\bar{12}\}. \end{align*} The classes $\bar{2}$ and $\bar{5}$ are not in this set, so they are quadratic non-residues modulo $13$. Their product satisfies \begin{align*} 2\cdot 5 = 10 \equiv 10 \pmod{13}, \end{align*} and $\bar{10}\in Q_{13}$, so two non-residues can multiply to a residue. On the other hand, $\bar{3}\in Q_{13}$ while $\bar{5}\notin Q_{13}$, and \begin{align*} 3\cdot 5 = 15 = 13+2 \equiv 2 \pmod{13}. \end{align*} Since $\bar{2}\notin Q_{13}$, this product shows that multiplying a residue by a non-residue can give a non-residue. [/example] The example is small, but the pattern is general because multiplication by any fixed non-residue moves the residue subgroup onto its complementary coset. The Legendre symbol is the homomorphism that records which coset a class lies in. ## Euler's Criterion and Computation ### The Power Test Listing all squares modulo $p$ is reliable for small primes and useless for large ones. We need a test that reads the answer directly from $a$ and $p$. Fermat's little theorem says $a^{p-1} \equiv 1 \pmod{p}$ for $p \nmid a$; [Euler's criterion](/theorems/1715) refines this by asking which square root of $1$ is obtained halfway through the exponent. [quotetheorem:1715] Euler's criterion turns the residue question into modular exponentiation. It is also the bridge between the elementary definition and multiplicative characters, because it expresses the Legendre symbol as a power map. [example: Testing Whether $2$ Is a Square Modulo $17$] Let $p=17$ and $a=2$. Since $17\nmid 2$, *Euler's Criterion* applies and tests the Legendre symbol by the power $2^{(17-1)/2}$. The exponent is \begin{align*} (17-1)/2 = 16/2 = 8. \end{align*} Now \begin{align*} 2^8 = 256 = 15\cdot 17 + 1. \end{align*} Therefore \begin{align*} 2^8 \equiv 1 \pmod{17}. \end{align*} By *Euler's Criterion*, this congruence means \begin{align*} \left(\frac{2}{17}\right)=1. \end{align*} So $2$ is a quadratic residue modulo $17$. One square root is visible from \begin{align*} 6^2 = 36 = 2\cdot 17 + 2. \end{align*} Thus \begin{align*} 6^2 \equiv 2 \pmod{17}. \end{align*} The power test proves that a square root exists, and the final congruence exhibits one explicitly. [/example] The same computation detects failure just as efficiently. A negative result is often more valuable than a square root, because it rules out entire families of congruence equations. [example: Certifying a Non-Residue] Let $p=19$ and $a=2$. Since $19\nmid 2$, *Euler's Criterion* applies with exponent \begin{align*} (19-1)/2 = 18/2 = 9. \end{align*} Compute the power by repeated multiplication: \begin{align*} 2^9 = 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2 = 512. \end{align*} To reduce $512$ modulo $19$, note that \begin{align*} 19\cdot 26 = 494. \end{align*} Therefore \begin{align*} 512 = 494+18 = 19\cdot 26+18. \end{align*} Since $18 \equiv -1 \pmod{19}$, this gives \begin{align*} 2^9 = 512 \equiv 18 \equiv -1 \pmod{19}. \end{align*} By *Euler's Criterion*, \begin{align*} \left(\frac{2}{19}\right)=-1. \end{align*} Thus $2$ is a quadratic non-residue modulo $19$, so the congruence $x^2 \equiv 2 \pmod{19}$ has no solution. [/example] ### Multiplicative Characters The examples show the power test acting like a sign. To make this computational behaviour reusable, we need the symbol to respect multiplication in the numerator. [quotetheorem:1716] Multiplicativity means that the Legendre symbol is a group homomorphism from $(\mathbb{Z}/p\mathbb{Z})^\times$ to $\{\pm 1\}$, extended by $0$ on multiples of $p$. This places quadratic residues among characters, a viewpoint that later generalises to Dirichlet characters and Gauss sums. ## Special Residues ### The Class of $-1$ A general test is powerful, but number theory often begins with special values. The class $-1$ is the first case where the answer depends only on a congruence condition on the prime. It asks whether the unit group modulo $p$ contains an element whose square is $-1$. The question whether $-1$ is a square modulo $p$ is the question whether there is an element of order $4$ in $(\mathbb{Z}/p\mathbb{Z})^\times$. Since that group has order $p-1$, the answer is governed by divisibility of $p-1$ by $4$. [quotetheorem:736] This criterion explains why $x^2+1$ sometimes has roots modulo primes and sometimes does not. It is a local arithmetic obstruction to solving the equation $x^2+1=0$. [example: Roots of $x^2+1$ Modulo Small Primes] Modulo $5$, the criterion *Criterion for $-1$ to Be a Quadratic Residue* predicts that $-1$ is a square because \begin{align*} 5 = 4+1 \equiv 1 \pmod{4}. \end{align*} The square root is visible from \begin{align*} 2^2 = 4. \end{align*} Since \begin{align*} 4 = 5-1, \end{align*} we get \begin{align*} 2^2 = 4 \equiv -1 \pmod{5}. \end{align*} Modulo $7$, the same criterion predicts that $-1$ is not a square because \begin{align*} 7 = 4+3 \equiv 3 \pmod{4}. \end{align*} Listing one representative from each pair $x,-x$ gives all non-zero squares modulo $7$: \begin{align*} 1^2 = 1 \equiv 1 \pmod{7}. \end{align*} \begin{align*} 2^2 = 4 \equiv 4 \pmod{7}. \end{align*} \begin{align*} 3^2 = 9 = 7+2 \equiv 2 \pmod{7}. \end{align*} Also, \begin{align*} -1 \equiv 6 \pmod{7}. \end{align*} Since $6$ is not among $1,2,4$, the congruence $x^2 \equiv -1 \pmod{7}$ has no solution. Thus the residue class of the prime modulo $4$ exactly predicts whether $x^2+1 \equiv 0 \pmod{p}$ has roots in these two cases. [/example] ### The Class of $2$ The class $2$ is subtler than $-1$. It is controlled not by congruence modulo $4$ but by congruence modulo $8$, so it reveals that quadratic residuosity can depend on finer arithmetic information about the prime. [quotetheorem:9933] The formula is compact but not opaque: $(p^2-1)/8$ is an integer for odd $p$, and its parity records the prime's class modulo $8$. This gives a fast way to decide many Pell-type and congruence questions involving powers of $2$. [example: The Modulo $8$ Pattern for $2$] For each odd prime $p$, *Supplementary Law for $2$* gives \begin{align*} \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}. \end{align*} For $p=7$, the exponent is \begin{align*} (7^2-1)/8=(49-1)/8=48/8=6. \end{align*} Thus \begin{align*} \left(\frac{2}{7}\right)=(-1)^6=1. \end{align*} An explicit square root is \begin{align*} 3^2=9=7+2\equiv 2 \pmod{7}. \end{align*} For $p=11$, the exponent is \begin{align*} (11^2-1)/8=(121-1)/8=120/8=15. \end{align*} Thus \begin{align*} \left(\frac{2}{11}\right)=(-1)^{15}=-1. \end{align*} The non-zero square classes can also be checked by listing one representative from each pair $x,-x$: \begin{align*} 1^2=1\equiv 1 \pmod{11}. \end{align*} \begin{align*} 2^2=4\equiv 4 \pmod{11}. \end{align*} \begin{align*} 3^2=9\equiv 9 \pmod{11}. \end{align*} \begin{align*} 4^2=16=11+5\equiv 5 \pmod{11}. \end{align*} \begin{align*} 5^2=25=2\cdot 11+3\equiv 3 \pmod{11}. \end{align*} Every remaining non-zero class modulo $11$ is the negative of one of $1,2,3,4,5$, and $(-x)^2=x^2$, so the non-zero squares modulo $11$ are exactly $1,3,4,5,9$. Since $2$ is not in this list, $2$ is not a square modulo $11$. For $p=17$, the exponent is \begin{align*} (17^2-1)/8=(289-1)/8=288/8=36. \end{align*} Thus \begin{align*} \left(\frac{2}{17}\right)=(-1)^{36}=1. \end{align*} This agrees with the exhibited square root \begin{align*} 6^2=36=2\cdot 17+2\equiv 2 \pmod{17}. \end{align*} These three primes represent the pattern modulo $8$: $2$ is a square for primes congruent to $1$ or $7$ modulo $8$, and a non-square for primes congruent to $3$ or $5$ modulo $8$. [/example] These special laws are not isolated tricks. They are the first visible pieces of a larger reciprocity principle, where the question whether $q$ is a square modulo $p$ is related to the question whether $p$ is a square modulo $q$. ## Quadratic Reciprocity The central miracle of quadratic residues is that two different primes can test each other. At first sight, the solvability of $x^2 \equiv q \pmod{p}$ should depend on the arithmetic of the field with $p$ elements, while the solvability of $y^2 \equiv p \pmod{q}$ should depend on the field with $q$ elements. Quadratic reciprocity says these two questions are almost the same, with a sign correction when both primes are $3$ modulo $4$. [quotetheorem:1721] Quadratic reciprocity changes the computational direction. To decide whether a large prime $q$ is a square modulo a smaller prime $p$, we may often swap the primes, reduce the larger one modulo the smaller one, and combine the result with the supplementary laws. [example: Using Reciprocity to Compute $\left(\frac{5}{23}\right)$] Both $5$ and $23$ are odd primes. By *Quadratic Reciprocity*, \begin{align*} \left(\frac{5}{23}\right)\left(\frac{23}{5}\right)=(-1)^{((5-1)/2)((23-1)/2)}. \end{align*} The exponent is \begin{align*} ((5-1)/2)((23-1)/2)=(4/2)(22/2)=2\cdot 11=22. \end{align*} Since $22$ is even, \begin{align*} (-1)^{22}=1. \end{align*} Thus \begin{align*} \left(\frac{5}{23}\right)\left(\frac{23}{5}\right)=1. \end{align*} The value $\left(\frac{23}{5}\right)$ is either $1$ or $-1$, so multiplying both sides by $\left(\frac{23}{5}\right)$ gives \begin{align*} \left(\frac{5}{23}\right)=\left(\frac{23}{5}\right). \end{align*} Now reduce the numerator $23$ modulo $5$: \begin{align*} 23=4\cdot 5+3. \end{align*} Hence \begin{align*} 23\equiv 3 \pmod{5}. \end{align*} The Legendre symbol depends only on the residue class of the numerator modulo the denominator, so \begin{align*} \left(\frac{23}{5}\right)=\left(\frac{3}{5}\right). \end{align*} To evaluate $\left(\frac{3}{5}\right)$, list the non-zero squares modulo $5$: \begin{align*} 1^2=1\equiv 1 \pmod{5}. \end{align*} \begin{align*} 2^2=4\equiv 4 \pmod{5}. \end{align*} \begin{align*} 3^2=9=5+4\equiv 4 \pmod{5}. \end{align*} \begin{align*} 4^2=16=3\cdot 5+1\equiv 1 \pmod{5}. \end{align*} Therefore the non-zero square classes modulo $5$ are exactly $1$ and $4$. Since $3$ is not among them, \begin{align*} \left(\frac{3}{5}\right)=-1. \end{align*} Combining the equalities gives \begin{align*} \left(\frac{5}{23}\right)=\left(\frac{23}{5}\right)=\left(\frac{3}{5}\right)=-1. \end{align*} Thus $5$ is a quadratic non-residue modulo $23$, so the congruence $x^2\equiv 5 \pmod{23}$ has no solution. [/example] The sign in reciprocity is the only obstruction to complete symmetry. When both primes are $3$ modulo $4$, the swap changes the answer. [example: The Sign Change Case] Take $p=3$ and $q=7$. Both are odd primes, and \begin{align*} 3 = 0\cdot 4+3 \equiv 3 \pmod{4}. \end{align*} Also, \begin{align*} 7 = 1\cdot 4+3 \equiv 3 \pmod{4}. \end{align*} Thus this is the sign-change case in *Quadratic Reciprocity*, so \begin{align*} \left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right). \end{align*} Now reduce the numerator $7$ modulo $3$: \begin{align*} 7=2\cdot 3+1. \end{align*} Hence \begin{align*} 7\equiv 1 \pmod{3}. \end{align*} The Legendre symbol depends only on the numerator's residue class modulo the denominator, so \begin{align*} \left(\frac{7}{3}\right)=\left(\frac{1}{3}\right). \end{align*} Since \begin{align*} 1^2=1\equiv 1 \pmod{3}, \end{align*} the class $1$ is a quadratic residue modulo $3$, and therefore \begin{align*} \left(\frac{1}{3}\right)=1. \end{align*} Substituting this into the reciprocity equality gives \begin{align*} \left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right)=-1. \end{align*} This agrees with the square list modulo $7$. One representative from each pair $x,-x$ is enough because $(-x)^2=x^2$, and \begin{align*} 1^2=1\equiv 1 \pmod{7}. \end{align*} \begin{align*} 2^2=4\equiv 4 \pmod{7}. \end{align*} \begin{align*} 3^2=9=7+2\equiv 2 \pmod{7}. \end{align*} Thus the non-zero square classes modulo $7$ are $1,2,4$. Since $3$ is not in this list, $3$ is a quadratic non-residue modulo $7$, exactly as $\left(\frac{3}{7}\right)=-1$ says. [/example] Reciprocity is most effective when used together with factorisation. Multiplicativity reduces composite numerators to prime numerators, and the supplementary laws handle the factors $-1$ and $2$. ## Composite Moduli and the Jacobi Symbol Many congruences are asked modulo an odd composite number $n$, not just modulo a prime. A solution modulo $n$ is equivalent to compatible solutions modulo the prime powers dividing $n$, so the prime case remains the foundation. However, the Legendre symbol itself is only defined for prime denominators. The Jacobi symbol extends the notation to odd composite denominators. Before defining the extension, we need the denominator to be split into prime factors. The point of the definition is not to assert solvability modulo $n$, but to preserve the multiplicative calculus of symbols. [definition: Jacobi Symbol] Let $n \ge 3$ be an odd integer with prime factorisation $n = \prod_{i=1}^r p_i^{e_i}$. The Jacobi symbol modulo $n$ is the function \begin{align*} \left(\frac{\cdot}{n}\right): \mathbb{Z} \to \{-1,0,1\}. \end{align*} Its input-to-output rule is: for $a \in \mathbb{Z}$, \begin{align*} \left(\frac{a}{n}\right) = \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i}. \end{align*} [/definition] The Jacobi symbol agrees with the Legendre symbol when $n$ is prime. For composite $n$, we need to know exactly what information survives the compression from many prime tests to one sign. [quotetheorem:9934] The precise local test is stronger than the Jacobi symbol: if $n = \prod_{i=1}^r p_i^{e_i}$, then solving $x^2 \equiv a \pmod{n}$ is equivalent, by the [Chinese remainder theorem](/theorems/734), to solving $x^2 \equiv a \pmod{p_i^{e_i}}$ for every prime power $p_i^{e_i}$ dividing $n$. When $\gcd(a,n)=1$ and the primes are odd, solvability modulo $p_i^{e_i}$ is governed by solvability modulo $p_i$ via Hensel lifting. The Jacobi symbol only records the product of the prime-level Legendre symbols, so it can lose the separate prime-level signs needed to know which local congruences are soluble. The converse fails because the product defining the Jacobi symbol can hide an even number of local failures. This is a useful warning: a symbolic calculation may say $1$ even when no square root exists modulo the composite modulus. [example: Jacobi Symbol Equal to $1$ Without a Square Root] Let $n=15$ and $a=2$. Since \begin{align*} 15=3\cdot 5, \end{align*} the Jacobi symbol is the product of the corresponding Legendre symbols: \begin{align*} \left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right). \end{align*} Modulo $3$, the residue classes have squares \begin{align*} 0^2=0\equiv 0 \pmod{3}. \end{align*} \begin{align*} 1^2=1\equiv 1 \pmod{3}. \end{align*} \begin{align*} 2^2=4=3+1\equiv 1 \pmod{3}. \end{align*} Thus $2$ is not a square modulo $3$, so \begin{align*} \left(\frac{2}{3}\right)=-1. \end{align*} Modulo $5$, the residue classes have squares \begin{align*} 0^2=0\equiv 0 \pmod{5}. \end{align*} \begin{align*} 1^2=1\equiv 1 \pmod{5}. \end{align*} \begin{align*} 2^2=4\equiv 4 \pmod{5}. \end{align*} \begin{align*} 3^2=9=5+4\equiv 4 \pmod{5}. \end{align*} \begin{align*} 4^2=16=3\cdot 5+1\equiv 1 \pmod{5}. \end{align*} Thus $2$ is not a square modulo $5$, so \begin{align*} \left(\frac{2}{5}\right)=-1. \end{align*} Therefore \begin{align*} \left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=1. \end{align*} Nevertheless, the congruence $x^2\equiv 2 \pmod{15}$ has no solution. If such an integer $x$ existed, then reducing the same congruence modulo $3$ would give \begin{align*} x^2\equiv 2 \pmod{3}. \end{align*} But the square list modulo $3$ above shows that every square is congruent to $0$ or $1$ modulo $3$, never to $2$. This contradiction shows that no square root of $2$ exists modulo $15$, even though the Jacobi symbol equals $1$; for composite moduli, the Jacobi symbol gives only a necessary obstruction, not a sufficient test for solvability. [/example] This failure is precisely why the prime case remains the clean setting for the definition of a quadratic residue. Composite moduli require local information at each prime factor, and the Jacobi symbol intentionally compresses that information. ## Finding Square Roots Deciding whether a square root exists and finding one are different tasks. Euler's criterion gives a decision test, but it does not automatically produce $x$ with $x^2 \equiv a \pmod{p}$. In certain congruence classes of primes, there is a simple exponent formula. The case $p \equiv 3 \pmod{4}$ is the easiest because $(p+1)/4$ is an integer and converts Euler's criterion into an actual square root. [quotetheorem:1682] This theorem is a rare moment where the decision test also gives the witness. For primes in other congruence classes, algorithms such as Tonelli-Shanks use a non-residue to split the group structure more carefully. To describe those algorithms, it is helpful to name the extra input they require. A non-residue can act as a certificate that we have left the square subgroup. [definition: Quadratic Non-Residue Witness] Let $p$ be an odd prime. A quadratic non-residue witness modulo $p$ is an integer $z \in \mathbb{Z}$ such that \begin{align*} \left(\frac{z}{p}\right)=-1. \end{align*} [/definition] The term is algorithmic: such a $z$ certifies a class outside the square subgroup and can be used to navigate the two-primary part of $(\mathbb{Z}/p\mathbb{Z})^\times$. This is the input needed by the standard Tonelli-Shanks square-root algorithm. [example: A Direct Square Root Modulo $11$] Let $p=11$ and $a=5$. The prime $11$ is congruent to $3$ modulo $4$, because \begin{align*} 11=2\cdot 4+3. \end{align*} The class $5$ is a quadratic residue modulo $11$, since \begin{align*} 4^2=16=11+5\equiv 5 \pmod{11}. \end{align*} Thus $\left(\frac{5}{11}\right)=1$ by the definition of the Legendre symbol. Now *Square Root Formula for Primes Congruent to $3$ Modulo $4$* applies. The exponent is \begin{align*} (11+1)/4=12/4=3. \end{align*} Therefore the formula gives \begin{align*} x\equiv 5^3 \pmod{11}. \end{align*} Compute the power: \begin{align*} 5^3=5\cdot 5\cdot 5=125. \end{align*} Since \begin{align*} 125=11\cdot 11+4, \end{align*} we get \begin{align*} 5^3\equiv 4 \pmod{11}. \end{align*} So one square root produced by the formula is $x\equiv 4 \pmod{11}$. Checking the square gives \begin{align*} 4^2=16=11+5\equiv 5 \pmod{11}. \end{align*} The negative class gives the other root: \begin{align*} -4\equiv 7 \pmod{11}. \end{align*} Indeed, \begin{align*} 7^2=49=4\cdot 11+5\equiv 5 \pmod{11}. \end{align*} Thus the congruence $x^2\equiv 5 \pmod{11}$ has the two roots $x\equiv 4$ and $x\equiv 7 \pmod{11}$. [/example] Finding roots is not just a computational afterthought. In cryptography and computational number theory, the gap between deciding residuosity and extracting square roots carries information about factorisation, especially for composite moduli. ## Beyond and Connected Topics Quadratic residues are the entry point to [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory), where congruences, primitive roots, and reciprocity laws become systematic tools. The present chapter focuses on the prime-modulus theory, while the broader course context explains how these ideas interact with arithmetic functions and modular computation. They also connect naturally to [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets), because the underlying objects are residue classes, congruence relations, finite sets, and maps between quotient structures. The square map on $(\mathbb{Z}/p\mathbb{Z})^\times$ is a compact example of how an [equivalence relation](/page/Equivalence%20Relation) becomes an algebraic object. In algebraic number theory, quadratic residues are the local shadows of splitting behaviour in number fields. The condition that $a$ be a square modulo $p$ is closely related to how primes split in quadratic extensions, a theme developed in [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). Quadratic residuosity also appears in [Cambridge II Coding and Cryptography](/page/Cambridge%20II%20Coding%20and%20Cryptography). Algorithms that compute Legendre and Jacobi symbols are efficient, while extracting square roots modulo suitable composite moduli, especially products of two odd primes, can be as hard as factoring in important settings. This contrast is one reason quadratic residues appear in cryptographic protocols. A further direction is the theory of finite fields. Over $\mathbb{F}_q$ with $q$ odd, the same square-subgroup picture persists: the non-zero squares form an index two subgroup of $\mathbb{F}_q^\times$. The prime field case in this chapter is the template for that generalisation. ## References Androma, [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). Androma, [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory). Androma, [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). Androma, [Cambridge II Coding and Cryptography](/page/Cambridge%20II%20Coding%20and%20Cryptography). G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers* (1979). Kenneth Ireland and Michael Rosen, *A Classical Introduction to Modern Number Theory* (1990). Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, *An Introduction to the Theory of Numbers* (1991).