Codex @codex  0

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.

If $b,c$ have a common prime factor, both Jacobi symbols are zero, and the identity holds. Otherwise write $b={\prod }_i{p}_i$, $c={\prod }_j{q}_j$ with multiplicity. All cross-pairs of primes are distinct. Multiplying quadratic reciprocity over these pairs givesThe exponent factors as a product of two sums. The parity identity from part (i) makes it congruent modulo two to $[(b-1)/2][(c-1)/2]$. ThereforeThe same formula includes a denominator equal to one by the empty-product convention.

For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

For distinct odd primes $p,q$, quadratic reciprocity statesHere the Legendre symbol records whether a nonzero congruence class is a quadratic residue. The first supplementary law for quadratic reciprocity and second supplementary law for quadratic reciprocity giveThus minus one is a square exactly when $p\equiv 1(\mathrm{mod}4)$, and two is a square exactly when $p\equiv 1$ or $7(\mathrm{mod}8)$.

To test the specified congruence class, factor $111=3\cdot 37$. Since $2017\equiv 1(\mathrm{mod}4)$, multiplicativity of the Legendre symbol and quadratic reciprocity yieldThere is no sign change on swapping $19$ and $37$ because $37\equiv 1(\mathrm{mod}4)$. Finally $18=2\cdot 3^2$, so multiplicativity of the Legendre symbol gives $(18/19)=(2/19)=-1$, since $19\equiv 3(\mathrm{mod}8)$. Therefore

Write $P={\prod }_i{p}_i$, $Q={\prod }_j{q}_j$, counting repetitions. Since $P,Q$ are coprime, every pair $p_i,q_j$ consists of distinct odd prime numbers. Quadratic reciprocity for the Legendre symbol givesMultiplying over all $i,j$ and using multiplicativity of the Jacobi symbol yields the sign exponentby the odd-product parity identity proved in (b)(i). Thus the Jacobi reciprocity law isIf either integer is $1$, its factorization is empty and both sides equal $1$.

The primes $2,5$ both work, with the zero residue as a solution. For every other prime, multiplicativity of the Legendre symbol and quadratic reciprocity giveThe first factor is positive for $p\equiv 1,7(\mathrm{mod}8)$; the second is positive for $p\equiv 1,4(\mathrm{mod}5)$. They must have the same sign. The Chinese remainder theorem therefore yields

For odd $p\ne 5$, quadratic reciprocity has no sign factor because $5\equiv 1(\mathrm{mod}4)$:The nonzero squares modulo $5$ are $1,4$, so the answer for odd primes is $p\equiv 1,4(\mathrm{mod}5)$. The excluded-prime wording also allows $p=2$, where $5\equiv 1$ has a square root. Thus the full answer is

For $p>3$, quadratic reciprocity givesThe second Legendre symbol is $1$ when $p\equiv 1(\mathrm{mod}3)$ and $-1$ when $p\equiv 2(\mathrm{mod}3)$. Combining it with the sign determined by $p(\mathrm{mod}4)$ shows that a quadratic residue occurs precisely for

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

Let $N=pq$ with primes $p\equiv 1(\mathrm{mod}12)$ and $q\equiv 5(\mathrm{mod}12)$. quadratic reciprocity makes three a square modulo $p$; choose $r^2=3$ and impose $a=-3+2r(\mathrm{mod}p)$, $a=1(\mathrm{mod}q)$ by the Chinese remainder theorem. The curve has good reduction at both primes. Indeed its discriminant is $-16a^2(4a+27)$; the first condition could make a factor vanish only at $p=3$ or 11, while the second gives $a(4a+27)=31$ and the given residue class excludes $q=31$.

Doubling $P$ gives $x(2P)-1=(a^2+6a-3)/4$. This vanishes modulo $p$ and equals one modulo $q$. Modulo $p$ one also has $y(2P)=-1$, so $2P=-P$ and $3P$ is the identity. Modulo $q$ the addition is finite. Thus computing $3P$ modulo $N$ encounters a denominator whose greatest common divisor with $N$ is exactly $p$, revealing the factor. The numerator difference is minus two modulo $p$, so the failed inverse cannot be cancelled. This is a construction of successful elliptic curve method data from prescribed local group behavior.

Necessity follows by reducing modulo three. For a prime $p\equiv 1(\mathrm{mod}3)$, quadratic reciprocity gives $(-3/p)=1$, so the discriminant criterion for prime representation by a binary quadratic form constructs a primitive positive definite form of discriminant of a binary quadratic form $-12$ representing $p$. Reduction gives $|b|\le a\le c$ and $a\le 2$. The only primitive reduced form is $[1,0,3]$: the alternatives $[2,\pm 2,2]$ are not primitive. Integral equivalence preserves represented integers, establishing sufficiency.

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]