1
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ The four points $(0,0), (0,b), (a,0), (a,b)$ for a rectangle with the diagonal from $(0,0)$ bisecting it. What about the lattices points inside the two triangles? $\endgroup$
    – Somos
    Commented Jul 17, 2017 at 1:36

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .