1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.