4, then: is solvable if and only if is solvable. If p and q are congruent to 3 modulo 4, then: is solvable if and only if is not solvable. The last is immediately equivalent to the modern form stated in the introduction above. It is a simple exercise to prove that Legendre's and Gauss's statements are equivalent – it requires no more than the first supplement and the facts about multiplying residues and nonresidues. Proof Apparently, the shortest known proof yet was published by B. Veklych in the American Mathematical Monthly. Proofs of the supplements The value of the Legendre symbol of (used in the proof above) follows directly from Euler's criterion: by Euler's criterion, but both sides of this congruence are numbers of the form , so they must be equal. Whether is a quadratic residue can be concluded if we know the number of solutions of the equation with which can be solved by standard methods. Namely, all its solutions where can be grouped into octuplets of the form , and what is left are four solutions of the form and possibly four additional solutions where and , which exist precisely if is a quadratic residue. That is, is a quadratic residue precisely if the number of solutions of this equation is divisible by . And this equation can be solved in just the same way here as over the rational numbers: substitute , where we demand that (leaving out the two solutions ), then the original equation transforms into Here can have any value that does not make the denominator zero – for which there are possibilities (i.e. if is a residue, if not) – and also does not make zero, which excludes one more option, . Thus there are possibilities for , and so together with the two excluded solutions there are overall solutions of the original equation. Therefore, is a residue modulo if and only if divides . This is a reformulation of the condition stated above. History and alternative statements The theorem was formulated in many ways before its modern form: Euler and Legendre did not have Gauss's congruence notation, nor did Gauss have the Legendre symbol. In this article p and q always refer to distinct positive odd primes, and x and y to unspecified integers. Fermat Fermat proved (or claimed to have proved) a number of theorems about expressing a prime