The Supplementary Laws: (-1/p) and (2/p)

The first supplementary law is the arithmetic core of Fermat's theorem on <a class="wiki-link" href="/wiki/math-numthy-sums-of-two-squares" data-track="wiki_article.body.wiki_link">Sums of Two Squares</a>: an odd prime $p$ is expressible as $a^2+b^2$ if and only if $p\equiv1\pmod4$, and the "only if" direction, plus the key existence step in "if", both hinge on knowing when $-1$ is a QR mod $p$. This propagates into the theory of Gaussian integers $\mathbb{Z}[i]$, where a prime $p\equiv1\pmod4$ splits as a product of two conjugate Gaussian primes while $p\equiv3\pmod4$ remains inert — a basic case of splitting of primes in number fields. The second supplementary law governs splitting in the real quadratic ring $\mathbb{Z}[\sqrt2]$ and determines when $x^2-2$ factors mod $p$, which matters for factoring polynomials over finite fields and for constructing explicit quadratic residue codes in coding theory. Both laws appear as base cases inside the full statement and every proof of the Law of Quadratic Reciprocity, and both are used as elementary building blocks in algorithms that compute Legendre and Jacobi symbols efficiently (used inside primality tests such as the Solovay–Strassen test and inside quadratic sieve / index calculus methods in computational number theory and cryptography). In cryptography specifically, fast Legendre-symbol evaluation via reciprocity (including these supplementary cases) underlies efficient square-root extraction modulo primes, which is a subroutine in some digital signature and key-exchange constructions. In physics and combinatorics, quadratic residues mod $p$ (whose basic $\pm1,\pm2$ behavior these laws pin down) appear in constructions of Paley graphs and difference sets with strong pseudorandomness properties.

Ask the tutor: How do the supplementary laws combine with the full reciprocity law to compute $\left(\frac{a}{p}\right)$ for a completely general integer $a$?

Think of the nonzero residues $1,2,\dots,p-1$ modulo $p$ as forming a cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p-1$ under multiplication. Squaring is a group homomorphism from this cyclic group to itself, and its image — the quadratic residues — is exactly the unique subgroup of index $2$. So exactly half of the nonzero residues are QRs and half are NQRs. The question "is $-1$ a QR?" becomes: does $-1$, an element of order exactly $2$ (since $(-1)^2=1$ and $-1 \ne 1$ for $p$ odd), lie in that index-$2$ subgroup? Because the group is cyclic of order $p-1$, the unique element of order $2$ lies in the subgroup of squares precisely when the group has an element of order $4$ dividing evenly — equivalently when $4 \mid p-1$. This is the group-theoretic shadow of the first supplementary law; Euler's Criterion makes it computational. The second law, about $2$, has no such one-line group-theoretic shortcut — $2$ is just some element of the cyclic group, with no special algebraic distinction the way $-1$ has order $2$. Instead the proof goes through Gauss's Lemma, which counts how many of the "least positive residues" of $1\cdot2, 2\cdot2,\dots,\frac{p-1}{2}\cdot 2$ modulo $p$ exceed $p/2$; the parity of that count is $\left(\frac{2}{p}\right)$. This turns a group-theoretic question into an explicit counting problem, whose answer depends on $p \bmod 8$ because the count of "large" residues among $2,4,6,\dots,p-1$ depends on where $p/2$ falls relative to multiples of $2$, and that pattern repeats with period $8$ in $p$.

(Gauss's Lemma is assumed known as a prerequisite; we use it as a black box below, together with a standard counting sublemma proved from it.)

Example 1: Is $-1$ a QR mod $p=1009$? First check $1009$ is prime: it is not divisible by $2,3,5,7,11,13,17,19,23,29,31$ (indeed $31^2 = 961 < 1009 < 1024=32^2$, so trial division up to $31$ suffices), and one checks $1009/7 = 144.1\ldots$, $1009/11=91.7\ldots$, $1009/13=77.6\ldots$, $1009/17=59.4\ldots$, $1009/19=53.1\ldots$, $1009/23=43.9\ldots$, $1009/29=34.8\ldots$, $1009/31=32.5\ldots$, none integral, so $1009$ is prime. Now $1009 = 4\cdot 252 + 1$, so $1009 \equiv 1 \pmod 4$. By the First Supplementary Law, $\left(\frac{-1}{1009}\right) = 1$: $-1$ is a quadratic residue mod $1009$. Concretely this means there is an $x$ with $x^2 \equiv -1 \pmod{1009}$. We can even locate it via Euler's Criterion by trial (or Tonelli–Shanks in practice), but the supplementary law guarantees existence without any search: since $1009 \equiv 1\pmod 4$, Fermat's two-square theorem (whose proof uses exactly this fact) further guarantees $1009 = a^2+b^2$ for some integers $a,b$; indeed $1009 = 15^2 + 28^2 = 225+784$, matching $225+784=1009$. This is a preview of how the first supplementary law feeds directly into Sums of Two Squares.

Example 2: Is $2$ a QR mod $p = 8191$? First, $8191 = 2^{13}-1$ is the Mersenne prime $M_{13}$ (a known prime, confirmed since $2^{13}-1=8191$ has no small factors: not divisible by $3,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89$ — checking $89^2=7921<8191<8281=91^2$ so trial division to $90$ suffices, and one may directly verify $8191$ is prime via known Mersenne prime tables). Compute $8191 \bmod 8$. Since $8191 = 8\cdot 1023 + 7$ (check: $8\cdot 1023 = 8184$, and $8184+7=8191$), we get $8191 \equiv 7 \pmod 8$. By the Second Supplementary Law, since $7 \equiv -1 \pmod 8$, we get $\left(\frac{2}{8191}\right) = 1$: $2$ is a quadratic residue mod $8191$. As a check via the closed formula: $(p^2-1)/8 = (8191^2-1)/8$. Since $8191\equiv 7\equiv -1\pmod 8$ we showed above this exponent is even, consistent with $+1$. This tells us, for instance, that $x^2\equiv 2\pmod{8191}$ is solvable — relevant to factoring $x^2-2$ over $\mathbb F_{8191}$ and to the splitting of $8191$ in the ring $\mathbb Z[\sqrt2]$: since $2$ is a nonzero square mod $8191$, the prime $8191$ splits into two distinct prime ideals in $\mathbb{Z}[\sqrt2]$ rather than remaining inert.