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$
  • 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 Jul 17 '17 at 1:36
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$
1
$\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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.