# Clarification of a proof of Eisenstein's lemma

I'm working on a proof of quadratic reciprocity following Wikipedia's proof via Eisenstein, and one line in the proof seems unjustified:

On the other hand, by the definition of $r(u)$ and the floor function, $$\frac{qu}p = \left \lfloor \frac{qu}p\right \rfloor + \frac{r(u)}p,$$ and so since $p$ is odd and $u$ is even, we see that $\left \lfloor qu/p \right \rfloor$ and $r(u)$ are congruent modulo 2.

$p$ and $q$ here are distinct odd primes, $u$ is an even number $1\le u\le p-1$, and $r(u)=({qu\bmod p})$. A simple question, but I don't see how to derive the claim that $r(u)\equiv\left \lfloor qu/p \right \rfloor\pmod 2$ here.

Cross multiply by $p$:

$$qu = p \left \lfloor { qu \over p} \right \rfloor + r(u)$$

$u$ is even, so the left hand side of the equality is even, so congruent to $0$ modulo $2$; $p$ is odd, so congruent to $1$ modulo $2$ - so the equation modulo $2$ is:

$$0 \equiv \left \lfloor { qu \over p} \right \rfloor + r(u) \pmod 2$$

$-1$ is equivalent to $1$ modulo $2$, so after rearrangement:

$$\left \lfloor { qu \over p} \right \rfloor \equiv r(u) \pmod 2$$

• That's nicer than I thought it was going to be (no case analysis needed). +1 – Mario Carneiro Jun 18 '15 at 11:41