Codex @codex  0

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.

A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes $p,q$, define the two floor function sumsThe parity form of Gauss's lemma gives $(q/p)=(-1{)}^M$ and $(p/q)=(-1{)}^N$. In the open rectangle $0<x<p/2$, $0<y<q/2$, the line $y=qx/p$ separates $M$ points below it from $N$ points above it. None lies on the line, because $py=qx$ and coprimality would force $p\mid x$. The total is therefore $(p-1)(q-1)/4$. Combining that count with the parity identities gives quadratic reciprocity.^[ref]

For an odd prime $p$, the least quadratic nonresidue $n(p)$ is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo $p$.

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 number $p$, the nonzero residue classes form the multiplicative group of the finite field ${\mathbb{F}}_p$. Every class has a unique multiplicative inverse. A class equals its own inverse precisely when $x^2=1$, so $(x-1)(x+1)=0$ in the field and $x=1$ or $x=-1$.

For an odd prime, pair each remaining class with its distinct inverse. Each pair contributes one to the product, leavingFor $p=2$, the same congruence is $1\equiv -1(\mathrm{mod}2)$. This proves Wilson's theorem.

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus

Use the standard theorem on reduction of torsion points on an elliptic curve: at a prime of good reduction, reduction is injective on torsion whose order is prime to that prime. Reduction at $2$ implies that every odd-primary part of the rational torsion subgroup has order dividing $3$. Thus its only possible odd prime is $3$, and its $3$-primary part has order at most $3$. Reduction at $5$ injects the $2$-primary part into a group of order $9$, so that part is trivial. No other primary part can occur.

Consequently the torsion subgroup has order at most three. Since $P_1$ has exact order three,This argument uses only prime-to-residue-characteristic injectivity, and therefore avoids an unjustified claim of full torsion injectivity at the prime $2$.

Begin with two points at distance one. A ruler draws the line through two known points; a compass draws a circle with a known centre and a constructible radius. New points are intersections of such lines and circles. A real number is constructible when it occurs as a coordinate of a point obtained by finitely many such operations; a complex point is constructible when both coordinates are.

If current coordinates lie in a field $K\subseteq \mathbb{R}$, a line-line intersection solves linear equations over $K$, while line-circle or circle-circle intersections reduce to a quadratic equation over $K$. Thus each step requires at most adjoining a square root. Consequently every constructible number lies in a towerConversely field sums and differences are obtained by laying off segments, products and quotients by similar triangles, and a positive square root by the geometric-mean construction in a semicircle. Hence every real number in such a tower is constructible. This proves the quadratic-tower criterion, not merely its necessity.

In particular a constructible algebraic number has degree a power of two. Degree alone is not sufficient in general; the exact criterion is containment in a quadratic tower. Equivalently the Galois group of its normal closure is a finite two-group: a tower's normal closure remains a two-extension, and a two-group admits a chain of subgroups with successive index two, yielding the converse by Galois correspondence.

The standard impossibility results follow. Doubling a unit-volume cube requires $\sqrt[3]{2}$, whose polynomial $X^3-2$ is irreducible by Eisenstein and has degree three. Trisecting an arbitrary angle would in particular trisect $60$ degrees, requiring $2\cos 20^{\circ }$, a root of $X^3-3X-1$. This cubic has no rational root and is irreducible, so this construction is impossible, although some particular angles can be trisected. Squaring the unit circle requires side length $\sqrt{\pi }$, impossible because $\pi$ is transcendental whereas constructible numbers are algebraic.

For a regular $n$-gon, constructibility is equivalent to that of $e^{2\pi i/n}$. The cyclotomic extension is Galois of degree $\phi (n)$, so it is constructible exactly when this degree is a power of two. Writing the prime factorization of $n$ shows the equivalent conditionIndeed odd prime exponents must be one, and each $p_i-1$ must be a power of two. If $2^m+1$ is prime, $m$ must itself be a power of two by factoring when $m$ has an odd divisor. Conversely this factorization makes the cyclotomic Galois group a two-group and provides a quadratic tower. This gives both positive constructions, such as the regular seventeen-gon, and obstructions, such as the regular seven-gon.

Use the usual positive-definite convention for binary quadratic forms with negative discriminant. Reduction by integral changes of variables of determinant one produces a form $a{x}^2+bxy+c{y}^2$ with $|b|\le a\le c$, and with $b\ge 0$ on the boundary. For completeness, replacing $x$ by $x+ny$ makes $|b|\le a$; if then $c<a$, interchange the variables, reversing one sign to keep determinant one. The new positive leading coefficient is smaller. Repeating terminates and gives a reduced form.

For discriminant $-7$, $4ac-b^2=7$ and the reduction inequalities give $3a^2\le 7$. Thus $a=1$, $b$ is odd and $|b|\le 1$, and $c=2$. The boundary convention chooses $b=1$. Hence there is exactly one positive-definite equivalence class, represented by $x^2+xy+2y^2$.

For an odd prime $p\ne 7$ represented by this form, the identity $4p=(2x+y{)}^2+7y^2$ shows that $-7$ is a square modulo $p$. Here $p\nmid y$, because otherwise $p\mid x$ and $p^2$ would divide the represented number. Conversely, if $-7$ is a square modulo $p$, choose odd $b$ with $b^2\equiv -7(\mathrm{mod}p)$. Then $(p,b,(b^2+7)/(4p))$ is an integral positive-definite form of discriminant $-7$. By the preceding reduction it is equivalent to the given form, so its value $p$ at $(1,0)$ is represented by that form. Quadratic reciprocity gives $(-7/p)=(p/7)$, whose value is one precisely for $p\equiv 1,2,4(\mathrm{mod}7)$. The exceptional primes are represented: $2=Q(0,1)$ and $7=Q(1,-2)$. ThereforeWithout the positive-definite convention, the first printed assertion is false: $-x^2-xy-2y^2$ also has discriminant $-7$ but cannot be equivalent to a positive-definite form, because an invertible change of variables preserves its sign.

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

For coefficients $b_n$ supported on an interval of length $H$, write $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. The variance form of the large sieve statesThe constant is absolute. One may take the explicit right side $(Q^2+2\pi H)\sum |b_n{|}^2$, by orthogonality of roots of unity and the exponential-sum large sieve proved in Question 2.

Take $H=\lfloor N^2\rfloor$, $Q=N$, and $b_n$ the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. Applying the given smooth-number density with parameter $\epsilon /2$ giveswith a harmless adjustment of the constant for integer endpoints. If an odd prime $p\le N$ has least quadratic nonresidue $n(p)>N^{\epsilon }$, then $p>N^{\epsilon }$: a quadratic nonresidue always occurs among $1,\dots ,p-1$. Every prime factor of every selected smooth number is thus a nonzero quadratic residue modulo $p$. By the multiplicativity of the Legendre symbol, every selected number is a nonzero quadratic residue modulo $p$.

There are $(p-1)/2$ nonzero quadratic nonresidue classes, and $B_p(a)=0$ on all of them. Their contribution to the variance is at leastIf $R$ denotes the number of exceptional primes, the variance form of the large sieve, with $\sum |b_n{|}^2=B$, yields $R{B}^2\ll N^{2}B$. ConsequentlyThis is the bounded exceptional primes for least quadratic nonresidues argument. Using an interval of length $N^2$ is what matches the $Q^2$ term; an interval of length $N$ would not give a bounded exceptional set.

Take sieve level $D=x^{1/3}$ and coefficient cutoff $L=\sqrt{D}=x^{1/6}$. Let $\mathcal{P}$ be the finite set of odd primes at most $L$. Give $n=p+2$ one unit of weight for each prime $p\le x$. For an odd squarefree integer $d$ on these primes, the sieve distribution isThe residue $-2$ is coprime to every such $d$, and $g(p)=1/(p-1)\in (0,1)$ for all permitted primes. Values of $g$ outside the permitted set can be chosen arbitrarily in $(0,1)$ at primes and extended multiplicatively on squarefree integers.

For the Selberg sieve normalizing sum, $k(p)=g(p)/(1-g(p))=1/(p-2)$ andHere is a direct proof of this lower bound. Restrict the Euler product to $3\le p\le y=L^{1/4}$. The Mertens first theorem gives ${\sum }_{3\le p\le y}\log p/(p-1)=\log y+O(1)$, which is at most $\frac{1}{2}\log L$ for large $L$. The Mertens second theorem givesThe truncated Euler-product lower bound, with $\theta =1/2$, now gives $J\ge W/2\gg \log L$.

Use the minimizing Selberg sieve weights from Question 3. Their absolute values are at most one, so the Selberg least-common-multiple weights satisfy $|{\lambda }_d|\le 3^{\omega (d)}$. Parts (a) and (b) control the remainder:The first factor uses the Bombieri–Vinogradov theorem; $D=x^{1/3}$ is below $x^{1/2}/{\log }^{B}x$ for all sufficiently large $x$. The second uses the permitted ${\sum }_{q\le D}{9}^{\omega (q)}/\varphi (q)\ll {\log }^{9}D$. The PDF has the exponent nine, which the TeX transcribes incorrectly. Choose $A=14$ to obtain $O(x/{\log }^{3}x)$.

Every twin prime pair with $p+2>L$ survives the finite sieve, while the pairs with $p+2\le L$ number at most $L$. The Selberg upper-bound sieve thus givesTherefore the twin-prime count is $O(x/{\log }^{2}x)$. The finite cutoff on the forbidden primes is essential: sieving by all odd primes would also discard the large prime values $p+2$ that we are trying to count.

A pointed category has a zero object, both initial and terminal. Factoring through that object gives a zero morphism $0_{A,B}$ between any two objects. In this paper a semi-additive structure means commutative-monoid enrichment: every hom-set is a commutative monoid with additive zero, and composition distributes over addition in both variables. No existence of finite products in a category is included in this last definition. This convention matters for the final one-object example; under the stronger convention requiring finite biproducts, that example would not be a semi-additive category.

Let $c_{A,B}:A+B\to A\times B$ be the given canonical isomorphism. Transfer the coproduct injections across $c_{A,B}$, so $A\times B$ is also a coproduct in a category, with injectionsWrite ${\nabla }_B:B\times B\to B$ for the morphism whose composites with $i_1,i_2$ are both $1_B$. For $f,g:A\to B$, define the biproduct-induced addition of morphisms byThe zero is the existing zero morphism. We verify the laws from the universal properties, without assuming addition in advance.

All finite canonical maps from coproducts to products are isomorphisms, by induction from the binary ones and the zero object. Thus both $(B\times B)\times B$ and $B\times (B\times B)$ are ternary coproducts in a category. The two iterated fold maps to $B$ agree on each of the three injections, hence are equal. Applying this to $⟨f,g,h⟩$ gives associativity. The interchange $B\times B\to B\times B$ swaps the two injections, so its composite with ${\nabla }_B$ is ${\nabla }_B$, giving commutativity. Finally $⟨f,0⟩=i_{1}f$, so $f+0=f$, and similarly $0+f=f$.

Precomposition is additive because $⟨f,g⟩u=⟨fu,gu⟩$. For $v:B\to C$, the morphisms $v{\nabla }_B$ and ${\nabla }_C(v\times v)$ agree on both injections, so they agree; consequently $v(f+g)=vf+vg$. Composition with a zero morphism is zero. This proves the commutative-monoid enrichment.

It is unique. In any such enrichment, the additive zero morphisms agree with the pointed ones, since each map to or from the zero object belongs to a singleton hom-set. The projections of $i_1{p}_1+i_2{p}_2$ from $A\times B$ are respectively $p_1,p_2$ by bilinearity, soFor $A=B$, composing on the left by ${\nabla }_B$ and on the right by $⟨f,g⟩$ forces the displayed formula for $f+g$. Thus the biproducts determine exactly one such enrichment.

For the last part, the underlying one-object category has endomorphism monoid $(\mathbb{N},\cdot )$, including $0$, and identity $1$. Its usual addition gives a commutative-monoid enrichment. Any permutation $\sigma$ of the prime numbers extends, by unique prime factorization, to a multiplicative monoid automorphism ${\varphi }_{\sigma }:\mathbb{N}\to \mathbb{N}$, fixing $0,1$. Transport addition byThis is a commutative monoid operation with zero $0$, and multiplication distributes over it: applying ${\varphi }_{\sigma }$ reduces each distributive law to the ordinary one in $\mathbb{N}$. Thus each operation supplies a semi-additive structure on the same fixed composition law.

For each odd prime $p$, take $\sigma$ to interchange $2$ and $p$, fixing every other prime. ThenDifferent choices of $p$ give different additions, and there are infinitely many prime numbers. Hence there are infinitely many distinct semi-additive structures, even though these transported structures are isomorphic as enriched categories. The underlying one-object category has no terminal object, because its endomorphism set is not a singleton, so it indeed has no finite products in a category.

A nonzero congruence class modulo an odd prime is a quadratic nonresidue when it is not a square. In the convention of quadratic residue, zero belongs to neither class. Thus $3,5,6$ are the quadratic nonresidues modulo seven, while $2,6,7,8,10$ are the quadratic nonresidues modulo eleven. No integer $x$ satisfies $x^2\equiv 3(\mathrm{mod}7)$, as the complete square map under quadratic residue shows.

A quadratic nonresidue is not an arithmetic dead end: multiplying by any fixed quadratic nonresidue $n$ exchanges the quadratic residues and the quadratic nonresidues. If $nq$ were a square for a square $q$, division by $q$ would make $n$ a square. Hence $n{Q}_p$ consists entirely of quadratic nonresidues; it has $(p-1)/2$ elements, because multiplication by nonzero $n$ is a bijection. It therefore equals the entire other coset of the quadratic residue subgroup. Modulo seven, $3\{1,2,4\}=\{3,6,5\}$.

The product of two quadratic nonresidues is consequently a quadratic residue: write them as $n{q}_1,n{q}_2$ in that same coset, and their product is $n^2{q}_1{q}_2$, a square. For example, $3\cdot 5\equiv 1(\mathrm{mod}7)$, whereas $2\cdot 3\equiv 6(\mathrm{mod}7)$ remains a quadratic nonresidue. The multiplicativity of the Legendre symbol packages these rules as ordinary sign multiplication.

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.

The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime. It uses the decomposition of the prime minus one into an odd part and a power of two to successively correct a candidate root.

For a multiplicative monoid automorphism $\varphi :\mathbb{N}\to \mathbb{N}$ fixing $0$, define $a\oplus b={\varphi }^{-1}(\varphi (a)+\varphi (b))$. This transports a semiring structure to the fixed underlying multiplication, hence a commutative-monoid enrichment on its one-object category. Swapping prime $2$ with an odd prime $p$ gives $1\oplus 1=p$. Infinitely many such primes therefore give infinitely many distinct additions, although the transported enriched categories are isomorphic.