Eisenstein's lemma

Statement

Let $p$ be an odd prime and let $a$ be a positive integer with $p \nmid a$. Then $$\left(\frac{a}{p}\right) = (-1)^{\sum_{u} \lfloor a u / p \rfloor},$$ where the sum runs over the even integers $u = 2, 4, \dots, p - 1$, and $\left(\frac{a}{p}\right)$ is the Legendre symbol.

Remarks

For example, take $p = 7$ and $a = 3$. The sum is $\lfloor 6/7 \rfloor + \lfloor 12/7 \rfloor + \lfloor 18/7 \rfloor = 0 + 1 + 2 = 3$, so $\left(\frac{3}{7}\right) = -1$. A common variant holds for odd $a$: then $\left(\frac{a}{p}\right) = (-1)^{\sum_{k=1}^{(p-1)/2} \lfloor k a / p \rfloor}$. The proof is similar to the proof of Gauss's lemma. Eisenstein used the lemma in a proof of quadratic reciprocity that counts lattice points in a triangle.

Explanations

L1 human

The lemma turns the question "is $a$ a square modulo $p$?" into a count of integer parts of fractions. The parity of the count gives the answer.