the same 8 cases as Legendre: In the next Article he generalizes this to what are basically the rules for the Jacobi symbol (below). Letting A, A′, etc. represent any (prime or composite) positive numbers ≡ 1 (mod 4) and B, B′, etc. positive numbers ≡ 3 (mod 4): All of these cases take the form "if a prime is a residue (mod a composite), then the composite is a residue or nonresidue (mod the prime), depending on the congruences (mod 4)". He proves that these follow from cases 1) - 8). Gauss needed, and was able to prove, a lemma similar to the one Legendre needed: Gauss's Lemma. If p is a prime congruent to 1 modulo 8 then there exists an odd prime q such that: The proof of quadratic reciprocity uses complete induction. Gauss's Version in Legendre Symbols. These can be combined: Gauss's Combined Version in Legendre Symbols. Let In other words: Then: A number of proofs of the theorem, especially those based on Gauss sums or the splitting of primes in algebraic number fields, derive this formula. Other statements The statements in this section are equivalent to quadratic reciprocity: if, for example, Euler's version is assumed, the Legendre-Gauss version can be deduced from it, and vice versa. Euler's Formulation of Quadratic Reciprocity. If then This can be proven using Gauss's lemma. Quadratic Reciprocity (Gauss; Fourth Proof). Let a, b, c, ... be unequal positive odd primes, whose product is n, and let m be the number of them that are ≡ 3 (mod 4); check whether n/a is a residue of a, whether n/b is a residue of b, .... The number of nonresidues found will be even when m ≡ 0, 1 (mod 4), and it will be odd if m ≡ 2, 3 (mod 4). Gauss's fourth proof consists of proving this theorem (by comparing two formulas for the value of Gauss sums) and then restricting it to two primes. He then gives an example: Let a = 3, b = 5, c = 7, and d = 11. Three of these, 3, 7, and 11 ≡ 3 (mod 4), so m ≡ 3 (mod 4). 5×7×11 R 3; 3×7×11 R 5; 3×5×11 R 7; and 3×5×7 N 11, so there are an odd number of nonresidues. Eisenstein's Formulation of Quadratic Reciprocity. Assume Then Mordell's Formulation of Quadratic Reciprocity. Let a, b and c