# Prove an Elementary sum of floor function

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.

• You need an assumption on $a$ and $b$ that ensures the right hand side is an integer; relative primality is not enough. – Barry Cipra Aug 4 '20 at 9:42
• Ah yes, I forgot to write that they are odd. I believe this fixes the claim. – HotelTrivago Aug 4 '20 at 15:19
• As edited, the equation now agrees with metamorphy's more general answer. – Barry Cipra Aug 4 '20 at 15:28
• @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. – 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
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 is exactly $$|S_\geqslant|$$, the number of elements of $$S_\geqslant$$. Likewise $$\sum\limits_{0.
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. Thus, $$|S_=|=\lfloor(d-1)/2\rfloor$$, and finally $$\sum_{\substack{0
• 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). – Barry Cipra Aug 4 '20 at 15:31
• 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 – NotSoTrivial Aug 5 '20 at 16:32
• @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. – metamorphy Aug 5 '20 at 16:50