Concept
In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published. Of the elementary combinatorial proofs, there are two which apply types of double counting. One by Gotthold Eisenstein counts lattice points. Another applies Zolotarev's lemma to , expressed by the Chinese remainder theorem as and calculates the signature of a permutation. The shortest known proof also uses a simplified version of double counting, namely double counting modulo a fixed prime. Eisenstein's proof of quadratic reciprocity is a simplification of Gauss's third proof. It is more geometrically intuitive and requires less technical manipulation. The point of departure is "Eisenstein's lemma", which states that for distinct odd primes p, q, where denotes the floor function (the largest integer less than or equal to x), and where the sum is taken over the even integers u = 2, 4, 6, ..., p−1. For example, This result is very similar to Gauss's lemma, and can be proved in a similar fashion (proof given below). Using this representation of (q/p), the main argument is quite elegant. The sum counts the number of lattice points with even x-coordinate in the interior of the triangle ABC in the following diagram: Because each column has an even number of points (namely q−1 points), the number of such lattice points in the region BCYX is the same modulo 2 as the number of such points in the region CZY: Then by flipping the diagram in both axes, we see that the number of points with even x-coordinate inside CZY is the same as the number of points inside AXY having odd x-coordinates. This can be justified mathematically by noting that . The conclusion is that where μ is the total number of lattice points in the interior of AXY. Switching p and q, the same argument shows that where ν is the number of lattice points in the interior of WYA.