Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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)$.

share|cite|improve this answer
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 – David Stone May 21 '12 at 23:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.