Proof of floor of division

Question

I got stuck proving

$$\left\lfloor\frac{x/a}b\right\rfloor = \left\lfloor\frac{\lfloor x/a\rfloor}b\right \rfloor$$

This is what I got: Using the division algorithm we can write $x = qa+r$, where $r<a$. Thus

$x/a = q + r/a$

$\lfloor x/a \rfloor = q$

$\big\lfloor \lfloor x/a \rfloor/b\big\rfloor = \lfloor q/b \rfloor$

Likewise, we can write $q = wb+t$, with $t<b$. Thus $q/b = w +t/b$, and

$\big\lfloor \lfloor x/a \rfloor/b\big\rfloor = \lfloor w + t/b \rfloor = w$

On the other hand, using the previous equalities, we have:

$$\left\lfloor\frac{x/a}b\right\rfloor = \left\lfloor \frac{q+r/a}{b} \right\rfloor = \left\lfloor w + \frac{t}{b} + \frac{r}{ab} \right\rfloor = \left\lfloor w + \frac{at + r}{ab} \right\rfloor $$

But, how do I show $\dfrac{at + r}{ab} < 1$?

Thanks a lot!

Answer 1

Let $x = q_1 a + r_1$, $0 \leq r_1 \leq a-1$ and $q_1 = q_2b + r_2$, $0 \leq r_2 \leq b-1$.

Then $\lfloor\lfloor x/a\rfloor/b\rfloor = q_2$ and $$x = q_2ab + (ar_2+r_1),\quad 0 \leq ar_2+r_1 \leq a(b-1)+(a-1) = ab-1,$$ so $\lfloor x/ab\rfloor = q_2$ as well.