Codex @codex  0

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.

For every odd prime $p$, the Legendre symbol of $2$ isThus $2$ is a quadratic residue for $p\equiv 1,7(\mathrm{mod}8)$ and a quadratic nonresidue for $p\equiv 3,5(\mathrm{mod}8)$.

Apply Gauss's lemma to the representatives $2,4,\dots ,p-1$. With $m=(p-1)/2$, exactlyexceed $p/2$. For the four possible odd residues of $p$ modulo $8$, this count has the same parity as $(p^2-1)/8$. The lemma gives the formula. For example, at $p=7$ the representatives $2,4,6$ have two entries above $7/2$, giving $(2/7)=1$; indeed $3^2\equiv 2(\mathrm{mod}7)$.

The quadratic congruence $x^2\equiv -1(\mathrm{mod}p)$ is soluble exactly when $p=2$ or $p\equiv 1(\mathrm{mod}4)$. At $p=2$, take $x=1$.

For an odd prime $p$, any solution is nonzero modulo $p$. Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $m=(p-1)/2$ when $p\equiv 1(\mathrm{mod}4)$. Pairing opposite factors in the factorial givesWilson's theorem therefore gives $(m!{)}^2\equiv -1(\mathrm{mod}p)$, constructing a solution. For example, at $p=13$ the construction gives $6!\equiv 5(\mathrm{mod}13)$ and $5^2\equiv -1(\mathrm{mod}13)$. The criterion is the first supplementary law for quadratic reciprocity expressed as existence of a square 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.

For an odd prime $q$, the formsare primitive binary quadratic forms of discriminant of a binary quadratic form $-8q$. Their diagonal polynomial coefficients are positive, so they are positive definite, and $q\ge 3$ makes both satisfy the reduced positive definite binary quadratic form inequalities.

Their proper equivalence classes are distinct. The first represents one at $(1,0)$, but the second has minimum positive value two: if $y\ne 0$, $2x^2+q{y}^2\ge q\ge 3$, while $y=0$ and $x\ne 0$ give at least two. Since proper equivalence preserves represented integers, the two forms cannot be equivalent.

Thus $h(-8q)\ge 2$. If the class number of a negative discriminant is exactly two, these are all its primitive proper classes. That completeness hypothesis is the reason a local square test can select one specific form in prime representation when h of minus eight q equals two.

For an odd prime $p$, putThen $T=0$ if $p\equiv 1(\mathrm{mod}4)$, and $T\equiv 0(\mathrm{mod}p)$ for every $p>3$.

For the first statement, the first supplementary law for quadratic reciprocity gives $\chi (-1)=1$, where $\chi$ is the Legendre symbol. Pairing $a$ with $p-a$ givesThe same pairing in the complete Legendre-symbol sum shows that this half sum is zero, proving the exact equality.

For the second statement, multiplication by $2$ permutes the nonzero residue classes modulo $p$. Reducing the weighted sum modulo $p$ and using multiplicativity of the Legendre symbol therefore gives $T\equiv 2\chi (2)T(\mathrm{mod}p)$. The coefficient $2\chi (2)-1$ is either $1$ or $-3$, and hence is invertible for $p>3$. Thus $T\equiv 0(\mathrm{mod}p)$. The restriction is necessary: at $p=3$, $T=1-2=-1$.