$\sum_{i=0}^{\frac{(p-1)}{2}} [\frac{qi}{p}] + \sum_{i=0}^{\frac{(q-1)}{2}} [\frac{pi}{q}] = \frac{(p-1)(q-1)}{4}$ for distinct odd primes $p,q$

Question

Let $p$ and $q$ are distinct odd primes. Prove:

$$\sum_{i=0}^{\frac{(p-1)}{2}} [\frac{qi}{p}] + \sum_{i=0}^{\frac{(q-1)}{2}} [\frac{pi}{q}] = \frac{(p-1)(q-1)}{4}$$

$[x]$ is the greatest integer less than or equal to $x$

This is confusing to think about, because if we substitute $p = kq + r$, in the original, we have to deal with terms like $\frac{nr}{p}$, which can be anything. And I'm not sure what can be done other than substituting that back

Answer 1

This is one of those theorems where the algebra looks opaque and intimidating at first, but suddenly everything is crystal clear with the right picture.

Imagine drawing the grid of integer lattice points in the plane, and the line $y = px/q.$

Can you think of a geometric interpretation for each of those two sums?

Answer 2

I present an algebraic proof, instead of a geometric one.

Observe that we can write the sum as \begin{align*} \sum_{i=0}^{(p-1)/2}\left[\frac{qi}{p}\right]+\sum_{i=0}^{(q-1)/2}\left[\frac{pi}{q}\right]=\sum_{i=0}^{(p-1)/2}\sum_{1\leq j\leq qi/p}1+\sum_{i=0}^{(q-1)/2}\sum_{1\leq j\leq pi/q}1. \end{align*}

Interchanging the first summation (main tool), we get \begin{align*} \sum_{i=0}^{(p-1)/2}\sum_{1\leq j\leq qi/p}1+\sum_{i=0}^{(q-1)/2}\sum_{1\leq j\leq pi/q}1&=\sum_{1\leq j\leq\frac{q(p-1)}{2p}}\sum_{\frac{pj}{q}\leq i\leq \frac{p-1}{2}}1+\sum_{i=0}^{(q-1)/2}\sum_{1\leq j\leq \frac{pi}{q}}1 \\ &=\sum_{1\leq j<\frac{q}{2}}\sum_{\frac{pj}{q}\leq i<\frac{p}{2}}1+\sum_{1\leq i\leq\frac{q-1}{2}}\sum_{1\leq j\leq \frac{pi}{q}}1 \\ &=\sum_{1\leq j\leq\frac{q-1}{2}}\sum_{1\leq i\leq\frac{p-1}{2}}1-\sum_{1\leq j\leq\frac{q-1}{2}}\sum_{1\leq i<\frac{pj}{q}}1+\sum_{1\leq i\leq\frac{q-1}{2}}\sum_{1\leq j\leq \frac{pi}{q}}1 \\ &=\sum_{1\leq j\leq\frac{q-1}{2}}\sum_{1\leq i\leq\frac{p-1}{2}}1-\sum_{1\leq j\leq\frac{q-1}{2}}\sum_{1\leq i<\frac{pj}{q}}1+\sum_{1\leq i\leq\frac{q-1}{2}}\sum_{1\leq j<\frac{pi}{q}}1 \\ &=\sum_{1\leq j\leq\frac{q-1}{2}}\sum_{1\leq i\leq\frac{p-1}{2}}1=\frac{(p-1)(q-1)}{4} \end{align*}