How to prove $ \lfloor \frac{\lfloor\frac{a}{b}\rfloor}{c} \rfloor = \lfloor \frac{a}{b \times c} \rfloor $

Question

If $ a,b,c $ are positive integers, how to prove $ \lfloor \frac{\lfloor\frac{a}{b}\rfloor}{c} \rfloor = \lfloor \frac{a}{b \times c} \rfloor $

Answer 1

Given any integer $n $ and $m> 0$, the remainder theorem says there are unique integers $q,r $ so that $n=qm+r;0\le r <m $. It's easy to verify that $[\frac nm]=q $. (Because $qm\le n=qm+r <qm+m$ so $q\le \frac nm < q+1$).

So....

Let $a=bk+r ;0\le r <b$. Let $k=cm+s;0\le s <c $.

Then $[\frac ab]=k $ and $[\frac {[\frac ab]}c]=m $.

$a=(cm+s)b+r=m(bc)+(sb+r) $ where $0\le sb+r \le (c-1)b+r <bc$. So $[\frac {a}{bc}]=m $.

Answer 2

Let $a = b \cdot q_1 + r_1$, with $0 \leq r_1 \lt b$.

Then $\frac ab = q_1 + \frac{r_1}b$, and since $0 \leq r_1 \lt b$, we can say that

$$\lfloor \frac ab\rfloor = \lfloor q_1 + \frac{r_1}b \rfloor = q_1$$

Now let $q_1 = c \cdot q_2 + r_2$, with $0 \leq r_2 \lt c$.

Then $\frac {q_1}c = q_2 + \frac{r_2}c$, and since $0 \leq r_2 \lt c$, we can say that

$$\lfloor \frac{\lfloor\frac{a}{b}\rfloor}{c} \rfloor = \lfloor \frac {q_1}c \rfloor = \lfloor q_2 + \frac{r_2}c \rfloor = q_2$$

Now we consider $\lfloor \frac {a}{b c} \rfloor$. Using the same variables in the forms we used above, we say

\begin{align*} \frac {a}{b c} &= \frac {a/b}{c} \\ &= \frac{q_1 + \frac{r_1}b}c \\ &= \frac{(c\cdot q_2 + r_2) + \frac{r_1}b}c \\ &= \frac{c \cdot q_2}c + \frac{r_2}c + \frac{\frac{r_1}b}c \\ &= q_2 + \frac{r_2}c + \frac{r_1}b \cdot \frac1c \end{align*}

Now we take the floor. We know that $r_2 < c$, that $r_1 < b$, and that $0 < \frac 1c \le 1$ (since $c \in \mathbb{Z}^+$). Thus

$$\lfloor \frac {a}{b c} \rfloor = \lfloor q_2 + \frac{r_2}c + \frac{r_1}b \cdot \frac1c \rfloor = q_2$$

Hence $$\lfloor \frac{\lfloor\frac{a}{b}\rfloor}{c} \rfloor = q_2 = \lfloor \frac{a}{b \times c} \rfloor$$

Answer 3

$\left\lfloor\frac{\lfloor\frac ab\rfloor}c\right\rfloor$ is the greatest integer $t$ with $t\le\frac{\lfloor\frac ab\rfloor}c$, that is $ct\le\lfloor\frac ab\rfloor$. If $t$ is an integer, so is $ct$ and $ct\le\lfloor\frac ab\rfloor$ iff $ct\le\frac ab$, that is iff $bct\le a$.

So, $\left\lfloor\frac{\lfloor\frac ab\rfloor}c\right\rfloor$ is the greatest integer $t$ with $bct\le a$, that is $\left\lfloor\frac{\lfloor\frac ab\rfloor}c\right\rfloor$ is $\lfloor\frac{a}{bc}\rfloor$.