Proving that $ \sum_{i=1}^{b-1} \left\lfloor \frac{a}{b}i \right\rfloor = \sum_{j=1}^{a-1} \left\lfloor \frac{b}{a}j \right\rfloor $

Question

I am trying to solve the following problem:

Let $a$ and $b$ be integers greater than one which have no common divisors. Prove that:

$$ \sum_{i=1}^{b-1} \left\lfloor \frac{a}{b}i \right\rfloor = \sum_{j=1}^{a-1} \left\lfloor \frac{b}{a}j \right\rfloor $$

and find the value of this common sum.

I would like to know if you have any tips about how to approach this problem.

Here is what I've tried until now:

By computing the sum for a few cases, I noticed that the equality seems to be valid even when $a$ and $b$ have common divisors. So, ignoring this constraint and without loss of generality, I consider $a>b$, $a = b + n$.

Then we can write:

$$ \sum_{i=1}^{b-1} \left\lfloor \frac{a}{b}i \right\rfloor = \frac{b(b-1)}{2} + \sum_{i=1}^{b-1} \left\lfloor \frac{a-b}{b}i \right\rfloor = \frac{b(b-1)}{2} + \sum_{i=1}^{b-1} \left\lfloor \frac{n}{b}i \right\rfloor$$

and

$$ \sum_{j=1}^{a-1} \left\lfloor \frac{b}{a}j \right\rfloor = \frac{a(a-1)}{2} - \sum_{j=1}^{a-1} \left\lceil \frac{a-b}{a}j \right\rceil = \frac{a(a-1)}{2} - \sum_{j=1}^{a-1} \left\lceil \frac{n}{a}j \right\rceil$$

I am trying to use induction on $n$ to prove the equality, but I don't know if it is the best way to solve it.

Answer 1

Since $a$ and $b$ are coprime, the numbers $0,a,2a,\ldots,(b-1)a$ form a complete set of residues modulo $b.$ Hence, if $\{ia/b\}$ denotes the fractional part of $ia/b,$ and if $i\neq j$ are any two distinct elments of $\{0,1,\ldots,b-1\},$ then $b^{-1}\{ia/b\}\neq b^{-1}\{ja/b\},$ which implies that each $b^{-1}\{ia/b\}$ is a unique element of the set $\{0,1/b,2/b,\ldots,(b-1)/b\}.$ Hence $$\sum_{k=0}^{b-1}\left\lfloor\dfrac{ka}{b}\right\rfloor=\sum_{k=0}^{b-1}\dfrac{ka}{b}-\sum_{k=0}^{b-1}\left\{\dfrac{ka}{b}\right\}=\dfrac{a(b-1)}{2}-\dfrac{b-1}{2}=\dfrac{(a-1)(b-1)}{2}$$ because $\sum_{k=0}^{b-1}(ka)/b=(a/b)\sum_{k=0}^{b-1}k$ and $\sum_{k=0}^{b-1}\{ka/b\}=b^{-1}\sum_{k=0}^{b-1}k.$ Thus, by symmetry $$\sum_{k=0}^{b-1}\left\lfloor\dfrac{ka}{b}\right\rfloor=\dfrac{(a-1)(b-1)}{2}=\sum_{k=0}^{a-1}\left\lfloor\dfrac{kb}{a}\right\rfloor$$

Answer 2

Hint : use the change of variable $l=b-i$ in the first sum, and recall that we have $\lfloor -x \rfloor=-\lfloor x \rfloor -1$ whenever $x$ is not an integer (more precisely, we have $\lfloor -x \rfloor =-\lceil x \rceil$ for any $x\in \mathbb{R}$).

Answer 3

Please see my answer here, in which I show that $$\sum_{k=0}^{a-1} \left\lfloor k \frac{b}{a} \right\rfloor=\frac{ab-a-b+\gcd(a,b)}{2}. $$ Symmetry is then obvious.