Rewriting repeated integer division with multiplication

In many programming languages, such as C and C++, integer division of positive numbers is defined by simply ignoring the remainder. $5 / 2 == 2$.

In general, is it true of positive integers $a$, $b$, and $c$ that

$(a / b) / c$

will always give the same result as

$a / (b * c)$

We can assume that $b$ and $c$ can be multiplied with no overflow.

Solution 1:

This is very easy using the universal property of the floor function, viz. $$\rm n\le \lfloor r \rfloor \iff n\le r,\ \ \ for\ \ \ n\in \mathbb Z,\ r\in \mathbb R$$ Thus for $\rm\:0 < c\in \mathbb Z,\ r\in \mathbb R,\ $ (e.g. $\rm\:r = a/b\in\mathbb Q\:$ in your case) $$\rm\begin{eqnarray} &\rm n &\le&\:\rm\ \lfloor \lfloor r \rfloor / c\rfloor \\ \iff& \rm n &\le&\ \ \rm \lfloor r \rfloor / c \\ \iff& \rm cn &\le&\ \ \rm \lfloor r \rfloor \\ \iff& \rm cn &\le&\ \ \rm r \\ \iff& \rm n &\le&\ \ \rm r/c \\ \iff& \rm n &\le&\ \ \rm \lfloor r/c \rfloor \\[0.5em] \Rightarrow\ \ \rm \lfloor \lfloor r&\rm \rfloor / c\rfloor &=&\rm\ \ \lfloor r/c\rfloor \end{eqnarray}$$

since they are both $\le $ each other by choosing $\,\rm n\,$ equal to each above.

For $\rm\:r = a/b\:$ we get your special case $\rm\ \lfloor \lfloor a/b \rfloor / c\rfloor = \lfloor a/(bc)\rfloor. $

If you know a little category theory you can view this universal property of floor as a right adjoint to inclusion, e.g. see Arturo's answer here or see most any textbook on category theory. But, of course, one need not know any category theory to understand the above proof. Indeed, I've had success explaining this (and similar universal-inspired proofs) to bright high-school students.

Solution 2:

Note that $a$ has a unique representation as $k_1b+r_1$ where $0\leq r<b$. Here, the number $k_1$ is the result of of the integer division $a/b$. Also, $a$ has a unique representation as $l(bc)+s$, where $0\leq s<bc$, so that $a/(b\cdot c)=l$.

Now $k_1$ can be represented as $k_2c+r_2$, with $0\leq r_2<c$, giving that $(a/b)/c=k_2$. Note that $a=k_2(bc)+r_2b+r_1$ and that $$0\leq r_2b+r_1\leq(c-1)b+r_1<(c-1)b+b=cb.$$ By unicity of $l$ and $s$, it follows that $k_2=l$. In other words, $(a/b)/c$ is indeed the same number as $a/(b\cdot c)$.