Sum over k to p over 2 of Floor of 2kq over p

Theorem

Let $p \in \Z$ be an odd prime.

Let $q \in \Z$ be an odd integer and $p \nmid q$.

Then:

$\ds \sum_{0 \mathop \le k \mathop < p / 2} \floor {\dfrac {2 k q} p} \equiv \sum_{0 \mathop \le k \mathop < p / 2} \floor {\dfrac {k q} p} \pmod 2$

When $k < \dfrac p 4$ we have:

$\ds \floor {\dfrac {\paren {p - 1 - 2 k} q} p}$

$=$

$\ds \floor {q - \dfrac {\paren {2 k + 1} q} p}$

$\ds $

$=$

$\ds q + \floor {-\dfrac {\paren {2 k + 1} q} p}$

$\ds $

$=$

$\ds q - \ceiling {\dfrac {\paren {2 k + 1} q} p}$

$\ds $

$=$

$\ds q - 1 - \floor {\dfrac {\paren {2 k + 1} q} p}$

$\ds $

$\equiv$

$\ds \floor {\dfrac {\paren {2 k + 1} q} p}$

$\ds \pmod 2$

Here it is noted that $\dfrac {\paren {2 k + 1} q} p$ is not an integer, since we have:

$p \nmid q$

$p > \dfrac p 2 + 1 > 2 k + 1$

Thus it is possible to replace the last terms:

$\floor {\dfrac {\paren {p - 1} q} p}, \floor {\dfrac {\paren {p - 3} q} p}, \ldots$

by:

$\floor {\dfrac q p}, \floor {\dfrac {3 q} p}, \ldots$

The result follows.

$\blacksquare$