residues, or both non-residues :. So either : are both even, or they are both odd. The sum of these two expressions is which is an integer. Therefore, Legendre's attempt to prove reciprocity is based on a theorem of his: Legendre's Theorem. Let a, b and c be integers where any pair of the three are relatively prime. Moreover assume that at least one of ab, bc or ca is negative (i.e. they don't all have the same sign). If are solvable then the following equation has a nontrivial solution in integers: Example. Theorem I is handled by letting a ≡ 1 and b ≡ 3 (mod 4) be primes and assuming that and, contrary the theorem, that Then has a solution, and taking congruences (mod 4) leads to a contradiction. This technique doesn't work for Theorem VIII. Let b ≡ B ≡ 3 (mod 4), and assume Then if there is another prime p ≡ 1 (mod 4) such that the solvability of leads to a contradiction (mod 4). But Legendre was unable to prove there has to be such a prime p; he was later able to show that all that is required is: Legendre's Lemma. If p is a prime that is congruent to 1 modulo 4 then there exists an odd prime q such that but he couldn't prove that either. Hilbert symbol (below) discusses how techniques based on the existence of solutions to can be made to work. Gauss Gauss first proves the supplementary laws. He sets the basis for induction by proving the theorem for ±3 and ±5. Noting that it is easier to state for −3 and +5 than it is for +3 or −5, he states the general theorem in the form: If p is a prime of the form 4n + 1 then p, but if p is of the form 4n + 3 then −p, is a quadratic residue (resp. nonresidue) of every prime, which, with a positive sign, is a residue (resp. nonresidue) of p. In the next sentence, he christens it the "fundamental theorem" (Gauss never used the word "reciprocity"). Introducing the notation a R b (resp. a N b) to mean a is a quadratic residue (resp. nonresidue) (mod b), and letting a, a′, etc. represent positive primes ≡ 1 (mod 4) and b, b′, etc. positive primes ≡ 3 (mod 4), he breaks it out into