Codex @codex  0

If, for every $\eta >0$, the smooth numbers up to $T$ with all prime factors at most $T^{\eta }$ have density at least $\kappa (\eta )>0$, then for fixed $\epsilon >0$ there are only $O_{\epsilon }(1)$ primes $p\le N$ with $n(p)>N^{\epsilon }$. Apply the variance form of the large sieve to the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times $N^2$ times that count. The density assumption with $\eta =\epsilon /2$ finishes the argument.

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

For coprime positive odd integers $a,b$, the Jacobi symbol satisfies $(a/b)(b/a)=(-1{)}^{(a-1)(b-1)/4}$. It follows by factoring $a$ and $b$ into primes and multiplying the quadratic reciprocity for each prime pair; the parity of the sums of prime half-differences agrees with $(a-1)/2$ and $(b-1)/2$. A Jacobi symbol equal to one does not imply that its numerator is a quadratic residue for a composite denominator.

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

For an odd prime $p$ and any integers $a,b$, the Legendre symbol obeysIn particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$, where $a^{-1}$ is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: $(a{r}^2/p)=(a/p)$ for $p\nmid r$.^[ref]

The subgroup and coset arguments under quadratic residue and quadratic nonresidue prove the sign rule without computing a large power: square times square is square, square times nonsquare is nonsquare, and nonsquare times nonsquare is square. If either factor is zero modulo $p$, both sides of the identity vanish. On ${\mathbb{F}}_p^{\times }$, the Legendre symbol is thus a group homomorphism to $\{1,-1\}$ whose kernel of a group homomorphism is the quadratic residue subgroup. Viewed on all integers, it is a completely multiplicative function and a Dirichlet character modulo $p$.

For an original calculation, factor the numerator $30=2\cdot 3\cdot 5$. Modulo seven, $(30/7)=(2/7)(3/7)(5/7)=1\cdot (-1)\cdot (-1)=1$, agreeing with $30\equiv 2(\mathrm{mod}7)$. Modulo eleven, the signs are instead $-1,1,1$, giving $(30/11)=-1$, agreeing with $30\equiv 8(\mathrm{mod}11)$. The same factorization can therefore certify different square behavior at different prime numbers.

Alternatively, Euler's criterion gives $(ab{)}^{(p-1)/2}\equiv a^{(p-1)/2}{b}^{(p-1)/2}$ modulo $p$. For nonzero factors both sides correspond to signs in $\{1,-1\}$. Since $p$ is odd, these signs are distinct modulo $p$, so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.

For a prime $p\equiv 3(\mathrm{mod}8)$, apply two-isogeny descent to the congruent number elliptic curve $y^2=x^3-p^{2}x$ and its companion $y^2=x^3+4p^{2}x$. The first square-class image is exactly $\{1,-1,p,-p\}$, already supplied by 2-torsion. The second has only positive candidates $1,2,p,2p$. The quartic covering in a two-isogeny descent equations for $p$ and $2p$ are impossible modulo $p$, because $-1$ is not a quadratic residue. For $2$ the equation is $W^2=2U^4+2p^2{V}^4$. Coprimality forces $U,V$ odd and $W=2Z$; modulo sixteen this gives $2Z^2=1+9=10$, which is impossible. Thus the second image is trivial and the square-class index formula for two-isogeny descent gives rank zero. The same prime-reduction argument bounds its rational torsion by four, and it already has four rational 2-torsion points, so it has no rational point corresponding to a right triangle of area $p$.

If a squarefree positive $d$ has a prime divisor $p\equiv 3(\mathrm{mod}4)$, a unit of norm $-1$ in $\mathbb{Q}(\sqrt{d})$ would give $a^2-d{b}^2=-4$ for integers $a,b$. Modulo $p$ this makes $-1$ a quadratic residue, which is impossible. The obstruction is sufficient, not a full criterion for negative-norm units.

Complete the square-class map at the identity by $q(O)=1$; at the finite point $T=(0,0)$ its value is the class of $b$. For another rational point writeThese denominator powers follow because a negative valuation of $x$ forces the leading cubic term to dominate, so that valuation is even and the valuation of $y$ is three halves of it. The equation givesIf a prime $\ell \nmid b$ divides $r$, it does not divide the second factor, since $\ell \nmid s$. Thus $v_{\ell }(r)$ is even. All denominator valuations are even too. Every image class therefore has a representative which is a signed squarefree divisor of $b$, proving that $\mathrm{im}q$ is finite.

Use the standard 2-isogeny with kernel $\{O,T\}$ and dual isogeny satisfying $\hat{\varphi }\varphi =[2]$, $\varphi \hat{\varphi }=[2]$. Away from the exceptional points one may takeApplying the analogous isogeny to $E^{\prime }$ gives a curve with coefficients $4a,16b$; scaling its coordinates by $1/4,1/8$ gives the dual map back to $E$. The analogous descent map $q^{\prime }$ on $D$ has kernel $\varphi (C)$ and finite image. The sequenceis exact at the last two terms. Its outside groups are finite, identified with the two finite descent images, so $C/2C$ is finite.

For $E_p:y^2=x(x^2-p^2)$, the rational 2-torsion is $O,(0,0),(p,0),(-p,0)$, of order four. The first descent image is exactly $\{1,-1,p,-p\}$: these classes occur on the 2-torsion, and the divisor-support bound permits no others. The isogenous curve is $E_p^{\prime }:y^2=x(x^2+4p^2)$. Its real points have $x\ge 0$, so the second image lies in the four positive classes $\{1,2,p,2p\}$.

Here the kernel $\{O,(0,0)\}$ of the dual is contained in $\varphi (C)$, since $\varphi (\pm p,0)=(0,0)$. Thus the displayed map $D/\varphi (C)\to C/2C$ is injective, and exactness givesThe allowed rank formula makes the left side $2^{R+2}$, soNow consider the quartic relation. Normalize a nontrivial integer solution so that $p$ does not divide both $x,y$, by dividing them by $p$ and $z$ by $p^2$ whenever necessary. If $p\nmid x$, reduction modulo $p$ gives $x^4=2z^2$, with $z\ne 0$ modulo $p$, making $2$ a quadratic residue. If $p\mid x$, then $p\nmid y$ and $p\mid z$; write $x=pX$, $z=pZ$, divide by $p^2$, and reduce to get $y^4=2Z^2$ modulo $p$. Again $2$ is a square. ThereforeIf the class $2$ occurred in $\mathrm{im}{q}^{\prime }$, write the corresponding coordinate as $x^{\prime }=2u^2/v^2$. The curve equation then givesHere $u,v$ are nonzero coprime integers and $z$ is rational. Since $2z^2$ is an integer, its reduced denominator must be one, so $z$ is an integer too. For $p\equiv 3,5(\mathrm{mod}8)$ this contradicts the quartic obstruction. Hence class $2$ is absent. A subgroup of $\{1,2,p,2p\}$ omitting $2$ has order at most two, so $2^R\le 2$ and $R\le 1$.

For $p=5$, direct substitution verifies the nonintegral pointA rational torsion point would have integral coordinates by the preceding theorem, so this point has infinite order. Thus $R\ge 1$, and together with the upper bound,

The nonzero quadratic residues modulo five are $1,4$. The values of $x^3+x+1$ and the numbers of possible $y$ areThere are eight affine points and one point at infinity. Thus $\#E({\mathbb{F}}_5)=9$ and part(ii) gives $\boxed{\mathrm{tr}(\varphi )=5+1-9=-3}$. The curve is nonsingular, since its short-Weierstrass discriminant $-16(4+27)$ is nonzero modulo five.

The dual operation reverses products, so $\widehat{{\varphi }^2}=(\hat{\varphi }{)}^2$. Also $\varphi \hat{\varphi }=[5]$ and $\varphi +\hat{\varphi }=[-3]$. Squaring the latter identity givesTherefore $\boxed{\mathrm{tr}({\varphi }^2)=-1}$. Over ${\mathbb{F}}_{25}$ the Frobenius is ${\varphi }^2$, of degree $25$, soMore generally the Frobenius trace recurrence has $t_0=2$, $t_1=t$ and $t_j=t{t}_{j-1}-q{t}_{j-2}$; the square calculation is its first nontrivial case.

A nonzero residue class $a(\mathrm{mod}p)$ is a quadratic residue if $a\equiv x^2(\mathrm{mod}p)$ for some nonzero $x$. If it is a square, Fermat's little theorem gives $a^{(p-1)/2}=x^{p-1}\equiv 1$. Conversely, the map $x\mapsto x^2$ on the nonzero classes identifies exactly the pairs $\{x,-x\}$, giving $(p-1)/2$ distinct squares. They are all roots of $X^{(p-1)/2}-1$ over the field ${\mathbb{F}}_p$; a polynomial of this degree has at most that many roots. Its roots are therefore precisely the squares. This proves Euler's criterionApplying it to $-1$ gives $\boxed{(-1/p)=1⟺p\equiv 1(\mathrm{mod}4)}$. The exclusion of $a=0$ is the usual nonzero-residue convention needed for this equivalence.

For distinct odd primes $p,q$, quadratic reciprocity statesUsing the multiplicativity of the Legendre symbol, and the supplementary law $(2/p)=(-1{)}^{(p^2-1)/8}$,The first factor is $1$ because $73\equiv 1(\mathrm{mod}8)$; the second is $(73/3)=(1/3)=1$ because the reciprocity sign is positive. Thus $\boxed{73\text{ is a quadratic residue modulo }127}$.

For each $x\in {\mathbb{F}}_p$, count the roots of $y^2=x^3+x^2+x+1$, and add the identity at infinity. A nonzero quadratic residue gives two roots, zero gives one, and a nonsquare gives none. Equivalently, with the Legendre symbol extended by ${\chi }_p(0)=0$,The numbers of affine $y$ values, in increasing $x$ order starting at zero, areso the answer isAll four reductions are smooth algebraic curves: the original PDF gives the elliptic-curve discriminant $-2^8$, so these odd primes are primes of good reduction.

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

Let $g$ generate the cyclic group of nonzero residues, whose order $p-1=2^{2^n}$ is a power of two. Write $a=g^j$. Its multiplicative order is $(p-1)/\gcd (j,p-1)$, so it is a primitive root precisely when $j$ is odd. The quadratic residues are exactly the even powers of $g$. Thus the primitive roots are precisely the quadratic nonresidues, with nonzero residue classes understood.

For $n\ge 1$, $p\equiv 1(\mathrm{mod}4)$, so quadratic reciprocity gives $(7/p)=(p/7)$. Since $2^3\equiv 1(\mathrm{mod}7)$ and $2^n$ alternates between $1$ and $2$ modulo three, $p$ is respectively $3$ or $5$ modulo seven. The nonzero squares modulo seven are $1,2,4$. Consequently $(7/p)=-1$, andThere is a genuine endpoint exception if the printed form permits $n=0$: then $p=3$ and $7\equiv 1(\mathrm{mod}3)$, which has order one and is not primitive. The first equivalence remains true for $p=3$, but the final assertion requires excluding that prime.

Since $26\equiv 2(\mathrm{mod}4)$, the ring of integers is $\mathbb{Z}[\sqrt{26}]$ with discriminant $104$. Write $P=(2,ϵ+1)=(2,\sqrt{26})$ and $Q_{\pm }=(5,ϵ\pm 1)$. Reduction of $X^2-26$ modulo two gives a double root, and modulo five gives the roots $\pm 1$. Thus $N(P)=2$, $N(Q_{\pm })=5$, and $(5)=Q_{+}{Q}_{-}$. Directly $P^2=(4,2\sqrt{26},26)=(2)$, since $26-6\cdot 4=2$. The element $ϵ+1=6+\sqrt{26}$ belongs to $P$ and $Q_{+}$ and has field norm ten, so equality of ideal norms givesThe Minkowski bound is $\sqrt{104}/2=\sqrt{26}<6$, so every ideal class contains an integral ideal of ideal norm at most five. Three is inert and gives no prime ideal of ideal norm three; ideals of ideal norm four are $P^2$, principal. Thus the class group is generated by $P,Q_{+},Q_{-}$, and the displayed relations make every class either trivial or $[P]$. The class $[P]$ is nontrivial: a generator would have field norm $\pm 2$, but $x^2-26y^2=\pm 2$ would give $x^2\equiv 2$ or $11(\mathrm{mod}13)$, neither a quadratic residue. Hence the class number is two.

The unit $ϵ=5+\sqrt{26}$ has field norm $-1$. To show it is fundamental, suppose $1<u<ϵ$ is a positive real embedding of a unit $x+y\sqrt{26}$. Its conjugate is $\pm 1/u$, so $y=(u-u^{\prime })/(2\sqrt{26})$ is a positive integer less than two. Thus $y=1$, and $x^2-26=\pm 1$ forces $x=\pm 5$. Only $5+\sqrt{26}$ is greater than one, contrary to the strict inequality. Therefore no smaller unit exceeds one. Multiplying any positive unit by a suitable power of ${ϵ}^{-1}$ puts it in $[1,ϵ)$, proving that all units are $\pm {ϵ}^n$.

An element of field norm $\pm 10$ has principal ideal $P{Q}_{+}$ or $P{Q}_{-}$ by prime ideal factorization. The first is generated by $ϵ+1$; the second by $ϵ-1=4+\sqrt{26}$, of field norm $-10$. Two generators of the same principal ideal differ by a unit. Therefore all, and only, the integer solutions areThe two displayed signs are independent; multiplication by a norm-minus-one unit exchanges the two field norm signs.

Write $p=8k+7$. In Gauss's lemma, for the multiplier 2, precisely the integers $j$ with $p/4<j\le (p-1)/2$ give residues $2j>p/2$. Their number isIt is even, so the Legendre symbol $(2/p)=1$: 2 is a quadratic residue modulo $p$. For completeness, the sign rule follows by replacing those large residues by their negatives; the resulting absolute residues permute $1,\dots ,(p-1)/2$. Multiplying them and cancelling their nonzero product gives $2^{(p-1)/2}\equiv (-1{)}^{2k+2}=1(\mathrm{mod}p)$, equivalent to the residue assertion by Euler's criterion.

Now take the prime $p=2q+1$. The condition $q\equiv 3(\mathrm{mod}4)$ gives $p\equiv 7(\mathrm{mod}8)$, so $2^q\equiv 1(\mathrm{mod}p)$. Thus $p$ divides $2^q-1$. For integers $q>3$, $2^q-1>2q+1$ (true at 4 and preserved on increasing $q$), so this divisor is proper and $2^q-1$ is composite. At $q=3$, the divisor is the number itself: $2^3-1=2\cdot 3+1=7$. The congruence still holds, but it does not establish compositeness.

Suppose $x^2\equiv -1(\mathrm{mod}p)$. Then $x\ne 0$ modulo the prime number $p$, so Fermat's little theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. But $p=4m+3$ makes $(p-1)/2=2m+1$ odd, and thereforeThis contradicts $1\not\equiv -1(\mathrm{mod}p)$, since $p$ is odd. Thus $-1$ is not a quadratic residue modulo $p$. Apply part (a) to the finite field $F={\mathbb{F}}_p$: the pairs $F^2$ with the given operations form a field, and there are $p$ choices for each coordinate, so its cardinality is $\boxed{p^2}$.

In the multiplicative group ${\mathbb{F}}_p^{\times }$, the squaring map is a group homomorphism with kernel $\{1,-1\}$, since $p$ is odd. Every nonzero square therefore has exactly two square roots. There are $(p-1)/2$ quadratic residues and the same number of nonresidues, and consequently ${\sum }_{a=1}^{p-1}\left(\frac{a}{p}\right)=0$.

For $n{m}_n\equiv 1(\mathrm{mod}p)$, direct multiplication gives $n^2(1+m_n)\equiv n^2+n=n(n+1)$. Multiplicativity of the Legendre symbol, including its value zero on multiples of $p$, impliesInversion permutes ${\mathbb{F}}_p^{\times }$, so $1+m_n$ runs through all residue classes except $1$. Thus

Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}=1$ in this case. There are equally many nonzero quadratic residues and quadratic nonresidues, so ${\sum }_{n=1}^{p-1}\chi (n)=0$. Replacing $n$ by $p-n$ and using the multiplicativity of the Legendre symbol givesConsequently $\boxed{S=0}$.

Put $h=(p-1)/2$. The nonzero quadratic residues in the finite field ${\mathbb{F}}_p$ form a subgroup of size $h$: the group homomorphism $x\mapsto x^2$ has kernel $\{1,-1\}$. Each square satisfies $u^h=1$ by Fermat's little theorem. Since a nonzero polynomial of degree $h$ has at most $h$ roots of a polynomial, these are all the roots of $X^h-1$. For any other nonzero $u$, Fermat's theorem gives $(u^h{)}^2=1$, so $u^h=-1$. Thus Euler's criterion follows, and multiplication givesBoth sides are $1$ or $-1$, which are distinct modulo the odd prime number $p$, so $\chi (mn)=\chi (m)\chi (n)$. Taking $n=-1$ in Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}$, which is $1$ for $p\equiv 1(\mathrm{mod}4)$ and $-1$ for $p\equiv 3(\mathrm{mod}4)$.