Prove: If $a$ and $b$ are odd and relatively prime, $$\sum_{\substack{0 \lt x \lt b/2\\x \in Z}} \left\lfloor \frac{ax}{b} \right\rfloor + \sum_{\substack{0 \lt y \lt a/2\\y\in Z}} \left\lfloor \frac{by}{a} \right\rfloor = \frac{a-1}{2} \cdot \frac{b-1}{2}$$

I have already proved that if $a$ and $b$ are relatively prime, $\sum_{x=0}^{b-1} \left\lfloor \frac{ax}{b} \right\rfloor = \frac{(a-1)(b-1)}{2}$. My thinking was to possibly use this fact, and split this equation into 2 equations according to the separate variables and intervals. However, I am not sure how to split the equation into $a$ and $b$, so I'm lost on how to approach this problem.

Any help would be appreciated.

  • $\begingroup$ You need an assumption on $a$ and $b$ that ensures the right hand side is an integer; relative primality is not enough. $\endgroup$ – Barry Cipra Aug 4 '20 at 9:42
  • $\begingroup$ Ah yes, I forgot to write that they are odd. I believe this fixes the claim. $\endgroup$ – HotelTrivago Aug 4 '20 at 15:19
  • $\begingroup$ As edited, the equation now agrees with metamorphy's more general answer. $\endgroup$ – Barry Cipra Aug 4 '20 at 15:28
  • 1
    $\begingroup$ @HotelTrivago FYI, although you've already proven for $a$ & $b$ being relatively prime that $\sum_{x=0}^{b-1} \left\lfloor \frac{ax}{b} \right\rfloor = \frac{(a-1)(b-1)}{2}$, you may be interested in reading the $5$ answers/proofs of this in math.stackexchange.com/q/1248784/602049. $\endgroup$ – John Omielan Aug 4 '20 at 20:23

Let's derive a more general formula. For arbitrary positive integers $a,b$, consider $$\newcommand{bigfloor}[1]{\left\lfloor #1\right\rfloor}S=\{(x,y)\in\mathbb{Z}^2 : 0<x<b/2, 0<y<a/2\},\\S_\geqslant=\{(x,y)\in S : ax\geqslant by\},\\S_\leqslant=\{(x,y)\in S : ax\leqslant by\},\\S_==\{(x,y)\in S : ax=by\}.$$

Now, for $(x,y)\in S$, we have $ax\geqslant by\iff y\leqslant ax/b\iff y\leqslant\lfloor ax/b\rfloor$, thus the first sum $\sum\limits_{0<x<b/2}\lfloor ax/b\rfloor$ is exactly $|S_\geqslant|$, the number of elements of $S_\geqslant$. Likewise $\sum\limits_{0<y<a/2}\lfloor by/a\rfloor=|S_\leqslant|$.

Further, $$|S_\geqslant|+|S_\leqslant|=|S_\geqslant\cup S_\leqslant|+|S_\geqslant\cap S_\leqslant|=|S|+|S_=|,$$ and trivially $|S|=\lfloor(a-1)/2\rfloor\cdot\lfloor(b-1)/2\rfloor$. So, it remains to count up $|S_=|$.

But if $d=\gcd(a,b)$, then $ax=by$ holds for positive integers $x,y$ if and only if $x=bc/d$ and $y=ac/d$ for a positive integer $c$ (to recall why: if $(a/d)x=(b/d)y$, then $a/d$ divides $(b/d)y$, hence $a/d$ divides $y$ because $a/d$ and $b/d$ are relatively prime; similarly, $b/d$ divides $x$, which gives the "only if"; the "if" is trivial). For $(x,y)\in S_=$, we should have additionally $c<d/2$. Thus, $|S_=|=\lfloor(d-1)/2\rfloor$, and finally $$\sum_{\substack{0<x<b/2\\x\in\mathbb{Z}}}\bigfloor{\frac{ax}{b}}+\sum_{\substack{0<y<a/2\\y\in\mathbb{Z}}}\bigfloor{\frac{by}{a}}=\bigfloor{\frac{a-1}{2}}\bigfloor{\frac{b-1}{2}}+\bigfloor{\frac{\gcd(a,b)-1}{2}}.$$

  • 2
    $\begingroup$ I've changed "correct" to "more general," to reflect the OP's edit specifying $a$ and $b$ as odd (in addition to being relatively prime). $\endgroup$ – Barry Cipra Aug 4 '20 at 15:31
  • $\begingroup$ Thank you for the diligent response. COuld you clarify a bit more why $|S|=\lfloor(a-1)/2\rfloor\cdot\lfloor(b-1)/2\rfloor$? Thanks $\endgroup$ – NotSoTrivial Aug 5 '20 at 16:32
  • $\begingroup$ @KentuckyFriedChicken: Well, for a positive integer $c$, there are $\lfloor(c-1)/2\rfloor$ integers (strictly) between $0$ and $c/2$ (consider the cases of odd/even $c$ separately; btw I'm also using this to compute $|S_=|$). And $S$ is simply a Cartesian product of two such intervals of integers. $\endgroup$ – metamorphy Aug 5 '20 at 16:50

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.