Suppose we want to solve $x^2 \equiv a \pmod p$, where $p$ is an odd prime. For $p=7$ we can list all squares, but for a large prime this becomes a search without structure. The Legendre symbol is the device that turns the question "is $a$ a square modulo $p$?" into a multiplicative arithmetic function. The striking point is that being a square modulo $p$ is not merely a yes-or-no property. Among the non-zero residue classes, it is compatible with multiplication: two non-zero non-squares multiply to a square, a square times a non-square remains a non-square, and this pattern is exactly what the values $1$ and $-1$ record. [example: Squares Modulo $7$] Modulo $7$, we square each residue class representative $0,1,2,3,4,5,6$ and reduce the result modulo $7$: \begin{align*} 0^2=0 \equiv 0 \pmod 7, \quad 1^2=1 \equiv 1 \pmod 7, \quad 2^2=4 \equiv 4 \pmod 7, \quad 3^2=9 \equiv 2 \pmod 7. \end{align*} \begin{align*} 4^2=16 \equiv 2 \pmod 7, \quad 5^2=25 \equiv 4 \pmod 7, \quad 6^2=36 \equiv 1 \pmod 7. \end{align*} Thus the square classes modulo $7$ are exactly $0,1,2,4$. Excluding the zero class, the non-zero square classes are $1,2,4$, while the remaining non-zero classes $3,5,6$ are non-squares. Therefore $x^2 \equiv 2 \pmod 7$ has solutions, for example $x \equiv 3$ and $x \equiv 4 \pmod 7$, but $x^2 \equiv 3 \pmod 7$ has no solution because $3$ does not occur in the square table. [/example] This example shows the basic failure of brute force. A table answers one prime at one time, but it does not explain how square classes behave under multiplication or how to compare different primes. The first step is to name the square condition itself. ## Quadratic Residues and Non-Residues A [quadratic residue](/page/Quadratic%20Residue) is what appears in a square table modulo $p$. The definition is phrased using integers, but the condition depends only on residue classes modulo $p$. It captures the local square question that the whole page studies. [definition: Quadratic Residue Modulo an Odd Prime] Let $p$ be an odd prime. The quadratic-residue predicate modulo $p$ is the function \begin{align*} R_p: \mathbb{Z} &\to \{\text{true},\text{false}\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto R_p(a), \end{align*} where $R_p(a)=\text{true}$ if and only if there exists $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod p. \end{align*} An integer $a \in \mathbb{Z}$ is called a quadratic residue modulo $p$ if $R_p(a)=\text{true}$. [/definition] This page uses the inclusive convention: multiples of $p$ count as quadratic residues because the congruence is solved by $x \equiv 0 \pmod p$. Many number-theory arguments reserve the phrase "quadratic residue" for non-zero square classes, so we will explicitly say "non-zero quadratic residue" whenever the zero class must be excluded. The zero class satisfies the same equation with $x \equiv 0 \pmod p$, but it does not belong to the multiplicative group of non-zero residue classes. To discuss the failed square classes inside that group, we need a term that excludes multiples of $p$. This is the role of quadratic non-residue. [definition: Quadratic Non-Residue Modulo an Odd Prime] Let $p$ be an odd prime. The quadratic-non-residue predicate modulo $p$ is the function \begin{align*} N_p: \mathbb{Z} &\to \{\text{true},\text{false}\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto N_p(a), \end{align*} where $N_p(a)=\text{true}$ if and only if $p \nmid a$ and there is no $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod p. \end{align*} An integer $a \in \mathbb{Z}$ is called a quadratic non-residue modulo $p$ if $N_p(a)=\text{true}$. [/definition] ## Definition The next construction is needed because residue and non-residue terminology is too wordy for formulas. We want a single arithmetic function whose values can be multiplied, summed, and inserted into root-counting identities. The Legendre symbol is that function, with a special value for the zero class. [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 \{0,1,-1\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto \left(\frac{a}{p}\right), \end{align*} where \begin{align*} \left(\frac{a}{p}\right)&=0 \quad \text{if } p \mid a. \end{align*} \begin{align*} \left(\frac{a}{p}\right)&=1 \quad \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue modulo } p. \end{align*} \begin{align*} \left(\frac{a}{p}\right)&=-1 \quad \text{if } a \text{ is a quadratic non-residue modulo } p. \end{align*} [/definition] The symbol depends only on $a$ modulo $p$. It should be read as a function on residue classes, with the zero class separated because it is not invertible. [example: Reading the Symbol Modulo $7$] Modulo $7$, the square table from the previous example is \begin{align*} 0^2 \equiv 0,\quad 1^2 \equiv 1,\quad 2^2 \equiv 4,\quad 3^2 \equiv 2,\quad 4^2 \equiv 2,\quad 5^2 \equiv 4,\quad 6^2 \equiv 1 \pmod 7. \end{align*} Thus the classes represented by squares are $0,1,2,4$. By the definition of the Legendre symbol, the zero class gives $\left(\frac{0}{7}\right)=0$, the non-zero square classes give \begin{align*} \left(\frac{1}{7}\right)=1,\quad \left(\frac{2}{7}\right)=1,\quad \left(\frac{4}{7}\right)=1, \end{align*} and the remaining non-zero classes $3,5,6$ give \begin{align*} \left(\frac{3}{7}\right)=-1,\quad \left(\frac{5}{7}\right)=-1,\quad \left(\frac{6}{7}\right)=-1. \end{align*} For a numerator outside the list $0,\dots,6$, first reduce it modulo $7$. Since $10-3=7$, we have $10 \equiv 3 \pmod 7$, so \begin{align*} \left(\frac{10}{7}\right)=\left(\frac{3}{7}\right)=-1. \end{align*} Also, $-3-4=-7$, so $-3 \equiv 4 \pmod 7$, and therefore \begin{align*} \left(\frac{-3}{7}\right)=\left(\frac{4}{7}\right)=1. \end{align*} The value of the symbol is therefore determined by the residue class of the numerator modulo $7$, with the zero class separated from the non-zero square and non-square classes. [/example] ## Residues as a Multiplicative Question The non-zero residue classes modulo $p$ form the group $(\mathbb{Z}/p\mathbb{Z})^\times$. Squaring is a homomorphism on this group. This observation explains both how many non-zero squares there are and why the Legendre symbol is multiplicative. ### Half of the Non-Zero Classes A square table has repetitions because $x$ and $-x$ have the same square. For an odd prime, those are the only repetitions among non-zero residue classes. Hence the non-zero classes split into two equal parts: among the $p-1$ non-zero classes, exactly half are squares and half are non-squares. With the page's inclusive convention, the zero class is still a quadratic residue, but it is not part of this equal non-zero split. The equal split explains why the values $1$ and $-1$ occur equally often away from zero. Counting alone does not explain products. The structural reason is stronger: the non-zero square classes form a subgroup of $(\mathbb{Z}/p\mathbb{Z})^\times$ of index $2$, and multiplying by a fixed non-square swaps that subgroup with its complementary coset. Since products are the natural operation in $(\mathbb{Z}/p\mathbb{Z})^\times$, this subgroup picture also explains the computational rule for products: the symbol of a product is the product of the symbols. Multiplicativity is useful because it turns a numerator into factors that can be evaluated separately. The example below shows the most characteristic case: two non-residues can multiply to a residue because their two $-1$ values multiply to $1$. [example: Non-Residue Times Non-Residue] Modulo $7$, the square classes computed from $0,1,2,3,4,5,6$ are $0,1,2,4$. Hence $3$ and $5$ are not square classes modulo $7$, so \begin{align*} \left(\frac{3}{7}\right)=-1,\quad \left(\frac{5}{7}\right)=-1. \end{align*} Multiplying these values gives \begin{align*} \left(\frac{3}{7}\right)\left(\frac{5}{7}\right)=(-1)(-1)=1. \end{align*} On the other hand, the product of the numerators is $3\cdot 5=15$, and \begin{align*} 15-14=1. \end{align*} Therefore $15 \equiv 1 \pmod 7$, so the Legendre symbol depends on the same residue class as $1$: \begin{align*} \left(\frac{15}{7}\right)=\left(\frac{1}{7}\right). \end{align*} Since $1^2=1$, the class $1$ is a non-zero square modulo $7$, and thus \begin{align*} \left(\frac{15}{7}\right)=\left(\frac{1}{7}\right)=1. \end{align*} So in this concrete case two quadratic non-residues, $3$ and $5$, multiply to the quadratic residue $1$ modulo $7$. [/example] Addition behaves very differently. There is no additive law for the Legendre symbol, and quadratic residues do not form an additive subgroup. [example: Failure of Additive Intuition] Modulo $7$, the classes $1$ and $2$ are both quadratic residues: $1$ occurs because \begin{align*} 1^2=1 \equiv 1 \pmod 7, \end{align*} and $2$ occurs because \begin{align*} 3^2=9 \equiv 2 \pmod 7. \end{align*} Their sum is \begin{align*} 1+2=3 \equiv 3 \pmod 7. \end{align*} Checking all square classes modulo $7$ gives \begin{align*} 0^2\equiv 0,\quad 1^2\equiv 1,\quad 2^2\equiv 4,\quad 3^2\equiv 2,\quad 4^2\equiv 2,\quad 5^2\equiv 4,\quad 6^2\equiv 1 \pmod 7. \end{align*} Thus $3$ does not occur as a square modulo $7$, so $3$ is a quadratic non-residue. Therefore \begin{align*} \left(\frac{1}{7}\right)=1,\quad \left(\frac{2}{7}\right)=1,\quad \left(\frac{3}{7}\right)=-1. \end{align*} So adding two quadratic residues can produce a quadratic non-residue; the Legendre symbol records multiplicative behavior, not additive behavior. [/example] ### Primitive Roots and Powers The most concrete way to see the residue/non-residue split is to choose a primitive root. Since $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic, every non-zero class is a power of a single generator. Then square classes are exactly the even powers of that generator, while non-squares are the odd powers. This gives a compact computational model for the whole symbol. [definition: Primitive Root Modulo $p$] Let $p$ be an odd prime. The primitive-root predicate modulo $p$ is the function \begin{align*} P_p: \mathbb{Z} &\to \{\text{true},\text{false}\}. \end{align*} It is evaluated by the rule \begin{align*} g &\mapsto P_p(g), \end{align*} where $P_p(g)=\text{true}$ if and only if the residue class $\bar{g}$ generates the group $(\mathbb{Z}/p\mathbb{Z})^\times$. An integer $g \in \mathbb{Z}$ is called a primitive root modulo $p$ if $P_p(g)=\text{true}$. [/definition] Once such a generator is chosen, the Legendre symbol should no longer require solving $x^2 \equiv a \pmod p$ directly. The missing computational bridge is a theorem that converts square status into the parity of the exponent of $a$ in the cyclic ordering generated by $g$. Even powers of $g$ are already squares, while an odd power of $g$ differs from them by one factor of $g$, so the residue/non-residue split becomes visible in the exponent. [quotetheorem:10086] This primitive-root viewpoint is useful only after a primitive root has actually been chosen; it is not a shortcut for finding such a generator, and it does not remove the need to reduce $a$ to a nonzero residue class modulo $p$. Its value is organizational: it lists the nonzero residues as $1,g,g^2,\dots,g^{p-2}$ and then separates them by exponent parity. For example, if $a \equiv g^{2m} \pmod p$, then $a$ is visibly a square, while if $a \equiv g^{2m+1} \pmod p$, it lies in the complementary half of the [cyclic group](/page/Cyclic%20Group). This is the computational sense in which the Legendre symbol becomes a parity test once a primitive root is available. The same formulation also explains why [Euler's criterion](/theorems/1715) uses the exponent $(p-1)/2$: raising $\bar{g}^k$ to that power records precisely the parity of $k$. That observation points toward a broader viewpoint, where the Legendre symbol is treated not just as a residue test but as a multiplicative character. ### Character Viewpoint A group character is a homomorphism from a group, usually into $\mathbb{C}^\times$. The Legendre symbol has a zero value on the zero residue class, so its character interpretation comes either by restricting to $(\mathbb{Z}/p\mathbb{Z})^\times$ or by viewing it as a Dirichlet character extended by $0$ on non-units. This viewpoint matters because it connects elementary congruences to Dirichlet characters, finite Fourier analysis, and character sums. [definition: Quadratic Character Modulo $p$] Let $p$ be an odd prime. The quadratic character modulo $p$ is the function \begin{align*} \chi_p: \mathbb{Z} &\to \{0,1,-1\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto \chi_p(a)=\left(\frac{a}{p}\right). \end{align*} [/definition] The function $\chi_p$ is periodic modulo $p$ and takes the value $0$ on multiples of $p$. It becomes a character in the group-theoretic sense after passing to non-zero residue classes, where it restricts to a homomorphism $(\mathbb{Z}/p\mathbb{Z})^\times \to \{1,-1\}$. To justify the word character, the value of $\chi_p(a)$ cannot depend on the chosen integer representative of a non-zero residue class modulo $p$, and multiplication of residues must be reflected by multiplication of signs. This is the point where the Legendre symbol stops being only a solvability test for one congruence and becomes a homomorphism on $(\mathbb{Z}/p\mathbb{Z})^\times$. The square classes are exactly the elements that should map to $1$, so they appear as the kernel of that homomorphism. The next issue is therefore structural rather than computational: does the Legendre symbol actually respect multiplication on all non-zero residue classes, and does its kernel coincide with the subgroup of square classes? Establishing this packages quadratic residuosity into a group character, which is the form needed for later product formulas and reciprocity arguments. [quotetheorem:1716] This theorem is what makes the Legendre symbol usable as more than a notation for individual congruences. Multiplicativity says that quadratic residuosity behaves compatibly with products: multiplying two residues or two non-residues gives a residue, while multiplying a residue by a non-residue gives a non-residue. The restriction to residue classes not divisible by $p$ is essential, since multiples of $p$ all have symbol $0$ and do not lie in the unit group. The character viewpoint will later let products of Legendre symbols be reorganized without returning to explicit square roots modulo $p$. Before using that viewpoint in character sums, however, we need a reliable way to evaluate a single Legendre symbol. The definition asks whether a congruence has a square root, while computation needs a test that can be carried out directly in modular arithmetic. ## Euler's Criterion and Computation Euler's criterion supplies that test by replacing the search for a square root with one exponentiation. Since $(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1$, the power $(p-1)/2$ is the exponent that detects the two possible signs compatible with Fermat's little theorem. ### Power Test The power test is the first practical method for evaluating Legendre symbols. It is also the bridge from the definition of quadratic residue to the later character interpretation: the sign of $a^{(p-1)/2}$ modulo $p$ records exactly whether $a$ represents a square class or a non-square class. [quotetheorem:1715] Euler's criterion is often the fastest way to check a small example. It also explains why the Legendre symbol behaves like a multiplicative character: exponentiation turns products into products, and the resulting values are only $1$ and $-1$ for units modulo $p$. The next computation illustrates the criterion for one concrete residue class before the page returns to broader character behavior. [example: Computing $\left(\frac{5}{11}\right)$] Since $11$ is an odd prime and $11 \nmid 5$, *Euler's criterion* applies with exponent \begin{align*} (11-1)/2=10/2=5. \end{align*} First compute the needed powers modulo $11$: \begin{align*} 5^2=25=22+3=2\cdot 11+3 \equiv 3 \pmod {11}. \end{align*} Squaring both sides preserves congruence, so \begin{align*} (5^2)^2 \equiv 3^2=9 \pmod {11}. \end{align*} Therefore \begin{align*} 5^5=5(5^2)^2 \equiv 5\cdot 9=45=44+1=4\cdot 11+1 \equiv 1 \pmod {11}. \end{align*} By *Euler's criterion*, \begin{align*} 5^5 \equiv \left(\frac{5}{11}\right) \pmod {11}. \end{align*} Thus $\left(\frac{5}{11}\right) \equiv 1 \pmod {11}$. Since $11 \nmid 5$, the Legendre symbol is either $1$ or $-1$, and $-1 \not\equiv 1 \pmod {11}$, so \begin{align*} \left(\frac{5}{11}\right)=1. \end{align*} This agrees with the square table check, because \begin{align*} 4^2=16=11+5 \equiv 5 \pmod {11}. \end{align*} So $5$ is a quadratic residue modulo $11$. [/example] ### Gauss's Lemma Euler's criterion turns the Legendre symbol into exponentiation, but the supplementary law for $2$ and many proofs of reciprocity need a more geometric count. Instead of raising $a$ to a large power, multiply the first half of the non-zero classes by $a$ and watch how many representatives cross from the positive half to the negative half. [quotetheorem:1719] [Gauss's lemma](/theorems/858) packages the same square-status information in a sign count. The representatives $a,2a,\dots,\frac{p-1}{2}a$ are reduced to least absolute residues, and the Legendre symbol records only the parity of the terms that land on the negative side. Thus the exact locations of the representatives are less important than whether an odd or even number cross the midpoint. For example, modulo $11$ with $a=5$, the products $5,10,15,20,25$ have least absolute residues $5,-1,4,-2,3$. Two of them are negative, so the sign is $(-1)^2=1$, agreeing with $\left(\frac{5}{11}\right)=1$. This method requires $\gcd(a,p)=1$ and $p$ odd; without invertibility the paired residue argument breaks down. For $a=2$, the same crossing count becomes especially simple, because it only asks which doubles pass the midpoint of the interval. ### The Symbols of $-1$ and $2$ The numerator $-1$ occurs whenever a congruence asks whether a square can equal a negative class. Euler's criterion makes this case depend only on $p$ modulo $4$. This gives the first supplementary law. [quotetheorem:10087] This law tells us exactly when $-1$ has a square root modulo $p$. It is a simple test with a strong geometric interpretation: whether the finite field $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ of residue classes modulo $p$ contains a square root of $-1$. [example: Solving $x^2 \equiv -1 \pmod p$] For $p=13$, we have \begin{align*} 13=4\cdot 3+1, \end{align*} so $13 \equiv 1 \pmod 4$. By *Supplementary Law for $-1$*, this gives \begin{align*} \left(\frac{-1}{13}\right)=1. \end{align*} We can also exhibit a square root explicitly: \begin{align*} 5^2=25=26-1=2\cdot 13-1. \end{align*} Hence $25 \equiv -1 \pmod {13}$, so \begin{align*} 5^2 \equiv -1 \pmod {13}. \end{align*} Thus $x^2 \equiv -1 \pmod {13}$ has a solution, for example $x \equiv 5 \pmod {13}$. For $p=11$, we have \begin{align*} 11=4\cdot 2+3, \end{align*} so $11 \equiv 3 \pmod 4$. By *Supplementary Law for $-1$*, \begin{align*} \left(\frac{-1}{11}\right)=-1. \end{align*} By the definition of the Legendre symbol, the value $-1$ means that $-1$ is a quadratic non-residue modulo $11$. Therefore there is no residue class $x$ with \begin{align*} x^2 \equiv -1 \pmod {11}. \end{align*} The congruence $x^2 \equiv -1 \pmod p$ is therefore solvable for $p=13$ but not for $p=11$, exactly as the congruence class of $p$ modulo $4$ predicts. [/example] The next theorem is needed because computations rarely involve only odd numerators. Once a factor $2$ appears, the law for $-1$ gives no answer, and modulo $4$ information is too coarse. The square status of $2$ depends on $p$ modulo $8$, which makes this the second supplementary law. [quotetheorem:9933] Together with multiplicativity, the supplementary laws handle factors $-1$ and $2$. The remaining difficulty is how to exchange two odd prime roles. ## Quadratic Reciprocity The central theorem of the subject is [quadratic reciprocity](/theorems/1721). It compares the question whether $q$ is a square modulo $p$ with the question whether $p$ is a square modulo $q$. The answer is almost symmetric, except for a sign change when both primes are $3$ modulo $4$. [quotetheorem:1721] Quadratic reciprocity is powerful because it moves the difficult denominator to a smaller modulus after reducing the numerator. Repeated use of reciprocity and the supplementary laws gives a finite hand computation. [example: Computing $\left(\frac{17}{43}\right)$] Since \begin{align*} 17=4\cdot 4+1, \end{align*} we have $17 \equiv 1 \pmod 4$. Also $17$ and $43$ are distinct odd primes. By *Quadratic Reciprocity*, the sign does not change when one of the primes is congruent to $1$ modulo $4$, so \begin{align*} \left(\frac{17}{43}\right)=\left(\frac{43}{17}\right). \end{align*} Now reduce the numerator $43$ modulo $17$: \begin{align*} 43=2\cdot 17+9. \end{align*} Therefore $43 \equiv 9 \pmod {17}$, and by *the fact that the Legendre symbol depends only on the residue class modulo $p$*, \begin{align*} \left(\frac{43}{17}\right)=\left(\frac{9}{17}\right). \end{align*} The class $9$ is a non-zero square modulo $17$, because \begin{align*} 3^2=9 \equiv 9 \pmod {17}. \end{align*} Hence, by the definition of the Legendre symbol, \begin{align*} \left(\frac{9}{17}\right)=1. \end{align*} Combining the equalities gives \begin{align*} \left(\frac{17}{43}\right)=\left(\frac{43}{17}\right)=\left(\frac{9}{17}\right)=1. \end{align*} Thus $17$ is a quadratic residue modulo $43$: the computation proves that the congruence $x^2 \equiv 17 \pmod {43}$ has a solution. [/example] The sign in reciprocity matters. When both primes are $3$ modulo $4$, the swap changes the symbol by a minus sign. [example: The Sign Change in Reciprocity] Take $p=3$ and $q=7$. We have \begin{align*} 3=4\cdot 0+3, \end{align*} so $3 \equiv 3 \pmod 4$, and \begin{align*} 7=4\cdot 1+3, \end{align*} so $7 \equiv 3 \pmod 4$. Since both primes are congruent to $3$ modulo $4$, *Quadratic Reciprocity* gives \begin{align*} \left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right). \end{align*} Now \begin{align*} 7=2\cdot 3+1, \end{align*} so $7 \equiv 1 \pmod 3$. Because the Legendre symbol depends only on the numerator modulo the denominator, \begin{align*} \left(\frac{7}{3}\right)=\left(\frac{1}{3}\right). \end{align*} The class $1$ is a non-zero square modulo $3$, since \begin{align*} 1^2=1 \equiv 1 \pmod 3. \end{align*} Thus \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*} So the sign change is visible in the smallest case where both odd primes are $3$ modulo $4$. [/example] ## Congruence Equations and Counting The Legendre symbol first appears as a detector for $x^2 \equiv a \pmod p$. It also counts the number of solutions. Over an odd prime modulus, a non-zero square has exactly two roots, a non-square has none, and zero has one. [quotetheorem:10088] The value $0$ in the Legendre symbol makes this formula uniform. If $p \mid a$, the expression gives one solution, namely $x \equiv 0 \pmod p$. [example: Counting Roots Modulo $13$] For $a=3$ and $p=13$, Euler's criterion uses the exponent \begin{align*} (13-1)/2=12/2=6. \end{align*} Compute \begin{align*} 3^6=729=13\cdot 56+1. \end{align*} Hence \begin{align*} 3^6 \equiv 1 \pmod {13}. \end{align*} By *Euler's criterion*, \begin{align*} 3^6 \equiv \left(\frac{3}{13}\right) \pmod {13}. \end{align*} Since $13 \nmid 3$, the Legendre symbol is either $1$ or $-1$, and $-1 \not\equiv 1 \pmod {13}$, so \begin{align*} \left(\frac{3}{13}\right)=1. \end{align*} By *[Number of Solutions to a Quadratic Congruence](/theorems/10088)*, the number of residue classes satisfying $x^2 \equiv 3 \pmod {13}$ is \begin{align*} 1+\left(\frac{3}{13}\right)=1+1=2. \end{align*} The two roots can be seen explicitly: \begin{align*} 4^2=16=13+3 \equiv 3 \pmod {13}. \end{align*} \begin{align*} 9^2=81=6\cdot 13+3 \equiv 3 \pmod {13}. \end{align*} For $a=5$, the same exponent is $6$. First, \begin{align*} 5^2=25=26-1=2\cdot 13-1 \equiv -1 \pmod {13}. \end{align*} Cubing both sides gives \begin{align*} 5^6=(5^2)^3 \equiv (-1)^3=-1 \pmod {13}. \end{align*} By *Euler's criterion*, \begin{align*} \left(\frac{5}{13}\right)=-1. \end{align*} Therefore *Number of Solutions to a Quadratic Congruence* gives \begin{align*} 1+\left(\frac{5}{13}\right)=1+(-1)=0. \end{align*} So $x^2 \equiv 3 \pmod {13}$ has exactly two solutions, represented by $4$ and $9$, while $x^2 \equiv 5 \pmod {13}$ has no solution. [/example] Quadratic equations often appear as $ax^2+bx+c \equiv 0 \pmod p$, not just as pure square equations. Completing the square reduces them to a single square test. The quantity that remains after this reduction is the discriminant, so it needs its own name before the root-counting theorem can be stated. [definition: Discriminant of a Quadratic Polynomial] The discriminant of a quadratic polynomial is encoded by the function \begin{align*} \Delta: \{(a,b,c) \in \mathbb{Z}^3 : a \ne 0\} &\to \mathbb{Z}. \end{align*} It is evaluated by the rule \begin{align*} (a,b,c) &\mapsto b^2-4ac. \end{align*} For the quadratic polynomial $ax^2+bx+c$, its discriminant is $\Delta(a,b,c)$. [/definition] Modulo an odd prime with $p \nmid a$, division by $2a$ is valid, so the usual completing-the-square argument survives in modular arithmetic. The discriminant criterion is useful because it reduces the whole quadratic polynomial to one Legendre symbol. It turns a root-counting problem into a square-status problem for $\Delta$. [quotetheorem:10089] The criterion is especially efficient when the discriminant is small or has recognizable factors. [example: A Quadratic Polynomial Modulo $11$] Consider \begin{align*} 2x^2+3x+4 \equiv 0 \pmod {11}. \end{align*} Here $11$ is an odd prime and $11 \nmid 2$, so the discriminant criterion applies. For $a=2$, $b=3$, and $c=4$, the discriminant is \begin{align*} \Delta=b^2-4ac=3^2-4\cdot 2\cdot 4=9-32=-23. \end{align*} Since \begin{align*} -23=-3\cdot 11+10, \end{align*} we have \begin{align*} \Delta \equiv 10 \pmod {11}. \end{align*} Next, \begin{align*} 10-(-1)=11, \end{align*} so \begin{align*} 10 \equiv -1 \pmod {11}. \end{align*} Also \begin{align*} 11=4\cdot 2+3, \end{align*} so $11 \equiv 3 \pmod 4$. By *Supplementary Law for $-1$*, \begin{align*} \left(\frac{-1}{11}\right)=-1. \end{align*} By [periodicity of the Legendre symbol](/theorems/10090), \begin{align*} \left(\frac{10}{11}\right)=\left(\frac{-1}{11}\right)=-1. \end{align*} Because $\Delta \equiv 10 \pmod {11}$, periodicity also gives \begin{align*} \left(\frac{\Delta}{11}\right)=\left(\frac{10}{11}\right)=-1. \end{align*} By *[Quadratic Congruence Discriminant Criterion](/theorems/10089)*, the number of residue classes $x \in \mathbb{Z}/11\mathbb{Z}$ satisfying $2x^2+3x+4 \equiv 0 \pmod {11}$ is \begin{align*} 1+\left(\frac{\Delta}{11}\right)=1+(-1)=0. \end{align*} Hence the congruence has no solution modulo $11$. [/example] ## From Legendre to Jacobi and Characters The Legendre symbol is defined only when the denominator is an odd prime. Many computations involve odd composite moduli, and it is useful to keep a similar notation. The Jacobi symbol extends the Legendre symbol by multiplying over the prime factors of the denominator. [definition: Jacobi Symbol] Let $n \in \mathbb{N}$ be odd, and suppose $n=p_1p_2\cdots p_r$ with odd primes $p_i$, counted with multiplicity. The Jacobi symbol modulo $n$ is the function \begin{align*} \left(\frac{\cdot}{n}\right): \mathbb{Z} &\to \{0,1,-1\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto \left(\frac{a}{n}\right), \end{align*} defined by \begin{align*} \left(\frac{a}{n}\right)=\prod_{i=1}^r \left(\frac{a}{p_i}\right). \end{align*} [/definition] The Jacobi symbol is computationally convenient, but it no longer detects squares by itself. A Jacobi value of $-1$ proves that $a$ is not a square modulo $n$, while a value of $1$ may still hide a failure at some prime factor. [example: Jacobi Symbol Equal to $1$ Without a Square] Take $n=15=3\cdot 5$ and $a=2$. By the definition of the Jacobi symbol, \begin{align*} \left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right). \end{align*} Modulo $3$, the square classes are found from \begin{align*} 0^2\equiv 0,\quad 1^2\equiv 1,\quad 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 square classes are found from \begin{align*} 0^2\equiv 0,\quad 1^2\equiv 1,\quad 2^2=4\equiv 4,\quad 3^2=9=5+4\equiv 4,\quad 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*} However, $2$ is not a square modulo $15$. Indeed, if some integer $x$ satisfied \begin{align*} x^2\equiv 2 \pmod {15}, \end{align*} then $15 \mid x^2-2$. Since $3 \mid 15$, this would imply $3 \mid x^2-2$, hence \begin{align*} x^2\equiv 2 \pmod 3. \end{align*} But the square table modulo $3$ above shows that only $0$ and $1$ occur as square classes modulo $3$, not $2$. This contradiction shows that $x^2\equiv 2 \pmod {15}$ has no solution, even though $\left(\frac{2}{15}\right)=1$. Thus the Jacobi symbol is not a complete solvability test for composite moduli. [/example] Before using Legendre symbols in sums or Dirichlet characters, we need the symbol to be a periodic function modulo $p$. This is what lets us sum over a complete residue system. It also confirms that the symbol is attached to residue classes rather than to chosen integer representatives. [quotetheorem:10090] A periodic character can be summed over one full period. Since the Legendre symbol takes the value $1$ on exactly half of the non-zero classes and $-1$ on the other half, while the zero class contributes $0$, the complete-period sum cancels: \begin{align*} \sum_{a=0}^{p-1}\left(\frac{a}{p}\right)=0. \end{align*} This vanishing is a first example of cancellation in character sums. To see that such sums already contain more than bookkeeping, it is useful to shift one copy of the character and ask how often two neighbouring classes have prescribed square status. [quotetheorem:10091] This identity measures the correlation between the square status of $a$ and $a+h$. It is still elementary, but it points toward the deeper estimates for character sums that become central in analytic number theory. ## Beyond and Connected Topics The Legendre symbol sits at the meeting point of elementary congruences, finite fields, and algebraic number theory. In [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory), it belongs to the study of modular arithmetic, primitive roots, and quadratic reciprocity. It gives the first serious example of a multiplicative character carrying arithmetic information. The next elementary step is the Jacobi symbol and then Dirichlet characters. The Jacobi symbol keeps the reciprocity algorithm efficient for composite odd moduli, while Dirichlet characters turn periodic multiplicative functions into objects that can be studied using Dirichlet $L$-functions. In [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields), the Legendre symbol reappears as a local splitting test. For example, the value of $\left(\frac{d}{p}\right)$ often determines how a prime $p$ factors in a quadratic number field $\mathbb{Q}(\sqrt{d})$. This is the algebraic meaning behind the elementary question of whether $d$ is a square modulo $p$. The foundational set and congruence language belongs earlier in [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). The Legendre symbol is a good point where basic modular arithmetic becomes structural: residue classes form groups, homomorphisms matter, and computation is guided by theorems rather than search. ## References Androma, [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory). Androma, [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). Androma, [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). Ireland and Rosen, *A Classical Introduction to Modern Number Theory* (1990). Hardy and Wright, *An Introduction to the Theory of Numbers* (2008). Serre, *A Course in Arithmetic* (1973).