[Math] Is (a/b)/c equal to a/(b*c) for integer division

arithmeticelementary-number-theoryintegersprogramming

Let $\div$ denote a binary operator that returns the integer quotient of two integers, i.e. (assuming that both integers are positive) $a \div b = \left\lfloor \frac ab \right\rfloor$. This corresponds to the integer division operator in many programming languages (e.g. the // operator in Python).

I observed that, when $a$, $b$ and $c$ are positive integers, the values of $(a \div b) \div c$ and $a \div (b \times c)$ are equal.

I have tried to find a counter-example by using the following Python code, but wasn't able to find one:

from random import randint

while True:

    a = randint(1, 10000000000)
    b = randint(1, 10000)
    c = randint(1, 10000)

    lhs = a//b
    lhs = lhs//c

    rhs = a//(b *c)

    if lhs != rhs:
        print a, b, c
        break

Could anyone please provide a counter example if the assertion that I made is not true or a proof which shows that it is always true?

Additional Information:

  1. Please note that all the division operators used above correspond to integer division.
  2. The version of Python is 2.7.12.
  3. I asked this question on StackOverflow and it was suggested there, that I ask it here.
  4. I was not able to find a tag which says integer-division, so I didn't use it and any suggestions are welcome.

Best Answer

Write $a=qb+r$, with $0 \le r \lt b$, so that $a \div b=q$.

Then write $q=sc+t$, with $0 \le t \lt c$, so that $(a \div b) \div c=s$.

We now have $a=b(sc+t)+r=bcs+bt+r$. As $$\begin{aligned} bt+r &\le b(c-1)+(b-1) \\ &=bc-b+b-1 \\ &=bc-1, \end{aligned}$$ we have $a \div (bc)=s$.

Related Question