IMC 2013 · Day 2 · P7

Suppose first that $pq$ is even (which implies that $p$ and $q$ have opposite parities), and let $a_k = (-1)^{\lfloor \frac{k}{p} \rfloor + \lfloor \frac{k}{q} \rfloor}$. We show that $a_k + a_{pq-1-k} = 0$, so the terms on the left-and side of ($*$) cancel out in pairs.

For every positive integer $k$ we have $\left\{ \frac{k}{p} \right\} + \left\{ \frac{p-1-k}{p} \right\} = \frac{p-1}{p}$, hence $$\left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{pq-1-k}{p} \right\rfloor = \frac{k}{p} - \left\{ \frac{k}{p} \right\} + \frac{pq-1-k}{p} - \left\{ \frac{pq-1-k}{p} \right\} = \frac{pq-1}{p} - \frac{p-1}{p} = q - 1$$ and similarly $$\left\lfloor \frac{pq-1-k}{q} \right\rfloor + \left\lfloor \frac{k}{q} \right\rfloor = p - 1.$$ Since $p$ and $q$ have opposite parities, it follows that $\lfloor \frac{k}{p} \rfloor + \lfloor \frac{k}{q} \rfloor$ and $\lfloor \frac{pq-1-k}{p} \rfloor + \lfloor \frac{pq-1-k}{q} \rfloor$ have opposite parities and therefore $a_{pq-1-k} = -a_k$.

Now suppose that $pq$ is odd. For every index $k$, denote by $p_k$ and $q_k$ the remainders of $k$ modulo $p$ and $q$, respectively. (I.e., $0 \le p_k < p$ and $0 \le q_k < q$ such that $k \equiv p_k \pmod p$ and $k \equiv q_k \pmod q$.) Notice that $$\left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{q} \right\rfloor \equiv p \left\lfloor \frac{k}{p} \right\rfloor + q \left\lfloor \frac{k}{q} \right\rfloor = (k - p_k) + (k - q_k) \equiv p_k + q_k \pmod 2.$$ Since $p$ and $q$ are co-prime, by the Chinese remainder theorem the map $k \mapsto (p_k, q_k)$ is a bijection between the sets $\{0, 1, \dots, pq-1\}$ and $\{0, 1, \dots, p-1\} \times \{0, 1, \dots, q-1\}$. Hence $$\sum_{k=0}^{pq-1} (-1)^{\lfloor \frac{k}{p} \rfloor + \lfloor \frac{k}{q} \rfloor} = \sum_{k=0}^{pq-1} (-1)^{p_k + q_k} = \sum_{i=0}^{p-1} \sum_{j=0}^{q-1} (-1)^{i+j} = \left( \sum_{i=0}^{p-1} (-1)^i \right) \cdot \left( \sum_{j=0}^{q-1} (-1)^j \right) = 1.$$