Codex @codex  0

The first supplementary law for quadratic reciprocity isIt also follows immediately from Euler's criterion applied to $-1$.

Write $s=(a/p)$. If $p\mid a$, both sides of the proposed identity are zero. Otherwise $s=\pm 1$. The multiplicativity of the Legendre symbol and Euler's criterion giveFor the middle equality, Euler's congruence determines the sign exactly, since both the symbol and $s^{(p-1)/2}$ are in $\{1,-1\}$ and $p$ is odd.

Euler's criterion statesFor $p\nmid a$, the sign is $+1$ precisely for a quadratic residue and $-1$ for a quadratic nonresidue. For $p\mid a$, both sides are zero.

Again $s=(a/p)\in \{1,-1\}$. By Euler's criterion, $(s/p)=s^{(p-1)/2}$. If $p\equiv 1(\mathrm{mod}4)$, the exponent is even and the answer is one. If $p\equiv 3(\mathrm{mod}4)$, it is odd and the answer is $s$. Hence

Euler's criterion states that for $p\nmid a$,For a multiple of $p$, both the Legendre symbol and that positive power vanish modulo $p$, so the congruence extends to that case as well.

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

For distinct odd primes $p,q$, quadratic reciprocity isThe usual supplementary laws areThe first supplement also follows immediately by inserting $a=-1$ into Euler's criterion.

Euler's criterion states that, for an odd prime $p$ and $p\nmid a$,Thus this power is congruent to one for a nonzero square and to minus one for a nonsquare. The congruence also holds when $p\mid a$ if both sides are taken to be zero.

If $p$ divides $a$ or $b$, it divides their product and both sides of the proposed identity are zero. Otherwise use Euler's criterion and the ordinary exponent rule:Both sides are in $\{1,-1\}$, and these two values are distinct modulo the odd prime $p$. Hence the congruence is an equality:

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 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 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$.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

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 Solovay-Strassen primality test samples unit bases and rejects an odd candidate as composite when it finds an Euler witness. Every prime passes every base by Euler's criterion, while an odd composite passes a random base with probability at most one half.

For $n\ge 2$, the first order bound already gives $p\equiv 1(\mathrm{mod}8)$. The second supplementary law for quadratic reciprocity says that two is then a quadratic residue modulo $p$. Euler's criterion gives $2^{(p-1)/2}\equiv 1$, so its multiplicative order $2^{n+1}$ divides $(p-1)/2$. Thus $2^{n+2}\mid p-1$, further reducing the candidate factors. At $n=5$, $641=5\cdot 128+1$ meets this bound. The restriction matters: $F_1=5$ has factor five, which is not one modulo eight.