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!

  • 2
    $\begingroup$ $t \leq b-1$ and $r < a$. What can you infer? $\endgroup$ – user27126 Jan 14 '13 at 22:30

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.


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.