# 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.

-

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 \\ \\ \Rightarrow\ \ \rm \lfloor \lfloor r\!\!&\rm \rfloor / c\rfloor\ &=&\rm\ \ \lfloor r/c\rfloor \end{eqnarray}$$ since integers are equal iff they have equal predecessors, i.e.

$$\rm\:j = k\!\iff\! \{n:n\le j\} = \{n:n\le k\}\iff [\: n\le j\iff n\le k\:]\quad QED$$

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.

-
While both answers were helpful, I found this much easier to follow. –  David Stone May 21 '12 at 23:24
See also this question on universal properties of gcd and lcm and adjointness. –  Bill Dubuque May 24 '12 at 21:28

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)$.

-
I'm in doubt about the notation for $a/b$. Maybe it is more natural for computer scientists to just denote it by $a/b$. But I'm not a computer scientist... Any advice? –  Egbert May 21 '12 at 16:29
Most programming languages that I've seen simply use a/b, and if both a and b are integers, then the operation is performed with integer division. Python 3 introduced syntax that was in some other languages (that I don't know off the top of my head) of having 3 // 2 == 1 and 3 / 2 == 1.5 python.org/dev/peps/pep-0238 –  David Stone May 21 '12 at 23:05