Codex @codex  0

For an odd prime $p$, the Legendre symbol is $\boxed{(a/p)=0}$ if $p\mid a$, $\boxed{(a/p)=1}$ if $a$ is a nonzero square modulo $p$, and $\boxed{(a/p)=-1}$ otherwise. It depends only on the residue class of $a$.

Euler's criterion gives $(-1/p)=(-1{)}^{(p-1)/2}$. The Legendre symbol is multiplicative, so multiplying this sign by the result of (iv) yields

The Legendre symbol being one means $a$ is nonzero and a square modulo $p$. Take one root $r\ne 0$. Factoring $x^2-r^2=(x-r)(x+r)$ in the field shows that any root is $r$ or $-r$. Since $p$ is odd these are distinct. Thus there are exactly $\boxed{2}$ solutions.

A square residue modulo $p$ is a congruence class represented by $x^2$ for some integer $x$. For the final all-primes solvability statement, zero is included as a square. The Legendre symbol distinguishes the zero class from the nonzero square and nonsquare classes:When the term quadratic residue is reserved for nonzero classes, the zero case must be stated separately, as in this definition.

Euler's criterion states, for an odd prime $p$,Apply it to $a=-1$. The integer $(-1{)}^{(p-1)/2}$ is $1$ when $p\equiv 1(\mathrm{mod}4)$ and $-1$ when $p\equiv 3(\mathrm{mod}4)$. Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:This is the first supplementary law for quadratic reciprocity.

For an odd prime $p$, the Legendre symbol isIt depends only on the congruence class of the integer $a$. The values $1$ and $-1$ distinguish a nonzero quadratic residue from a quadratic nonresidue; zero is a separate case.

For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

For distinct odd primes $p,q$, quadratic reciprocity statesHere the Legendre symbol records whether a nonzero congruence class is a quadratic residue. The first supplementary law for quadratic reciprocity and second supplementary law for quadratic reciprocity giveThus minus one is a square exactly when $p\equiv 1(\mathrm{mod}4)$, and two is a square exactly when $p\equiv 1$ or $7(\mathrm{mod}8)$.

To test the specified congruence class, factor $111=3\cdot 37$. Since $2017\equiv 1(\mathrm{mod}4)$, multiplicativity of the Legendre symbol and quadratic reciprocity yieldThere is no sign change on swapping $19$ and $37$ because $37\equiv 1(\mathrm{mod}4)$. Finally $18=2\cdot 3^2$, so multiplicativity of the Legendre symbol gives $(18/19)=(2/19)=-1$, since $19\equiv 3(\mathrm{mod}8)$. Therefore

For an odd prime $p$, Euler's criterion statesFor $p\nmid a$, the Legendre symbol is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue; if $p\mid a$, both sides are zero.

The product is a single power because the arithmetic progression of exponents has sum $2017\cdot 2018/2$:Since $2017\equiv 1(\mathrm{mod}8)$, the second supplementary law for quadratic reciprocity gives $(2/2017)=1$. Hence Euler's criterion gives $2^{1008}\equiv 1(\mathrm{mod}2017)$. Reduce the exponent using $1009=1008+1$ and $2017=2\cdot 1008+1$:The least nonnegative remainder is therefore $2$.

If $P\equiv P^{\prime }(\mathrm{mod}Q)$, then $P\equiv P^{\prime }(\mathrm{mod}p)$ for each prime factor $p$ of $Q$. The Legendre symbol depends only on the numerator's residue class, so the corresponding factors agree. Also $\gcd (P,Q)=\gcd (P^{\prime },Q)$, covering the zero cases. Multiplying givesThe convention for denominator $1$ gives the same conclusion there.

The second supplementary law for the Legendre symbol is $(2/p)=(-1{)}^{(p^2-1)/8}$. To multiply these signs, observe that for odd $a,b$,Both factors in the numerator are divisible by $8$, so the right side is even. Applying this identity repeatedly to the prime factorization givesAgain the convention at $Q=1$ agrees.

The supplementary law for the Legendre symbol is $(-1/p)=(-1{)}^{(p-1)/2}$ for odd prime numbers $p$. For odd integers $a,b$,and the last term is even. Induction over the prime factors of $Q$ therefore gives ${\sum }_i(p_i-1)/2\equiv (Q-1)/2(\mathrm{mod}2)$. ConsequentlyFor $Q=1$ the exponent is zero.

Write $P={\prod }_i{p}_i$, $Q={\prod }_j{q}_j$, counting repetitions. Since $P,Q$ are coprime, every pair $p_i,q_j$ consists of distinct odd prime numbers. Quadratic reciprocity for the Legendre symbol givesMultiplying over all $i,j$ and using multiplicativity of the Jacobi symbol yields the sign exponentby the odd-product parity identity proved in (b)(i). Thus the Jacobi reciprocity law isIf either integer is $1$, its factorization is empty and both sides equal $1$.

Complete the square to obtain the equivalent quadratic congruenceHere $\gcd (1111,8093)=1$: the Euclidean algorithm has successive nonzero remainders $316,163,153,10,3,1$. If this modular congruence had a solution, the Jacobi symbol $(1111/8093)$ would be $1$, since a square coprime to an odd modulus has Legendre symbol $1$ at every prime factor. Calculate instead, using Jacobi reciprocity and reduction of numerators,Therefore there is no solution. This obstruction does not require a separate primality test for $8093$; the Jacobi symbol suffices.

For $p>3$, quadratic reciprocity givesThe second Legendre symbol is $1$ when $p\equiv 1(\mathrm{mod}3)$ and $-1$ when $p\equiv 2(\mathrm{mod}3)$. Combining it with the sign determined by $p(\mathrm{mod}4)$ shows that a quadratic residue occurs precisely for

For odd $p$ and $k\not\equiv 0(\mathrm{mod}p)$, take $E:y^2=x^3+kx$. If $p\equiv 3(\mathrm{mod}4)$, pairing $x$ with $-x$ cancels the Legendre symbols. If $p\equiv 1(\mathrm{mod}4)$, the coefficient formula for trace of Frobenius modulo p givesThe binomial coefficient is nonzero because every factorial involved is shorter than $p$. Thus the Trace of Frobenius is not zero in the second case.

For $\omega =e^{2\pi i/p}$ and the Legendre symbol $\chi$, the quadratic Gauss sum isIt equals $\sqrt{p}$ for $p\equiv 1(\mathrm{mod}4)$ and $i\sqrt{p}$ for $p\equiv 3(\mathrm{mod}4)$ with the standard choice of square root.

Quadratic reciprocity compares two questions: is the prime number $p$ a quadratic residue modulo $q$, and is $q$ a quadratic residue modulo $p$? Let $p,q$ be distinct odd primes. In terms of the Legendre symbol,The two Legendre symbols have opposite signs exactly when both primes are $3$ modulo $4$; otherwise they are equal. Their values are nonzero because the primes are distinct. Equal signs can mean two quadratic residues or two quadratic nonresidues: reciprocity compares the answers rather than declaring either answer positive.^[ref]

For a direct computation, the nonzero quadratic residues modulo $3,5,7$ are respectively $\{1\}$, $\{1,4\}$, and $\{1,2,4\}$. Squaring just $1,\dots ,(p-1)/2$ suffices because $x$ and $p-x$ have the same square modulo an odd prime $p$.The pair $3,7$ has a sign flip, whereas $5,7$ has two negative signs. These small quadratic residue tables make the distinction tangible.

The first supplementary law for quadratic reciprocity handles numerator $-1$, and the second supplementary law for quadratic reciprocity handles numerator $2$:For an odd prime $p$, $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$, while $2$ is a quadratic residue exactly when $p\equiv 1,7(\mathrm{mod}8)$. The remaining odd congruence classes modulo $8$, namely $3,5$, make $2$ a quadratic nonresidue. These laws fill the cases excluded from swapping distinct odd primes.^[ref]

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.