Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

up vote 3 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|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
add comment

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|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
1  
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
add comment

Your Answer

 
discard

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.