30
$\begingroup$

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.
$\endgroup$
12
  • 16
    $\begingroup$ Already proven in 1994. See Wikipedia. $\endgroup$ Dec 8, 2017 at 17:41
  • 7
    $\begingroup$ The difference between computing and mathematics is when b*c causes arithmetic overflow (e.g. 16b or 32b int). Then a/(b *c) should be 0 but instead it'll cause overflow. $\endgroup$
    – smci
    Dec 8, 2017 at 18:27
  • 7
    $\begingroup$ I answered this on StackOverflow a few months ago. $\endgroup$ Dec 8, 2017 at 18:42
  • 6
    $\begingroup$ IMO, whoever told you to move this here was mistaken. While this question may indeed fall marginally within the scope of Math.SE (and could be made a better fit here with some editing to generalize it and make it less Python-specific), it would've been a much better fit for SO, or perhaps for Computer Science. SO's scope does seem to be gradually shifting towards "fix my code", with some folks there nowadays flat out claiming that any question without code to debug is off-topic (even though officially it's not). IMO, this is unfortunate. $\endgroup$ Dec 8, 2017 at 19:46
  • 3
    $\begingroup$ @IlmariKaronen: I'm very well aware of that, but the title merely says " integer division", and the body says "in many languages" and doesn't restrict the scope to Python, it only mentions it. This is a very real issue in C/C++/R/Java/SQL/assembly/Fortran/etc. $\endgroup$
    – smci
    Dec 8, 2017 at 20:24

6 Answers 6

48
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ The initial bound on $bt + r$ took me a while to understand. Perhaps a statement clarifying the switch from $t < c$ to $t \le c-1$, and $r < b$ to $r \le b-1$, is in order? That seems like the central trick. $\endgroup$ Dec 9, 2017 at 4:34
  • 2
    $\begingroup$ @DanielR.Collins: this takes advantage of the discreteness of the integers. If you are less than one you are less than or equal to the one below. The neat thing is I get two $-1$s and I need both of them. $\endgroup$ Dec 9, 2017 at 4:48
  • 3
    $\begingroup$ Yes, I know; I'm suggesting the detail be added to the answer. $\endgroup$ Dec 9, 2017 at 4:54
  • $\begingroup$ @DanielR.Collins: It seems my answer is a much easier way to do it, just by applying the division algorithm with $bc$ first instead of $b$ first. No need to play with ones. =) $\endgroup$
    – user21820
    Dec 10, 2017 at 8:17
4
$\begingroup$

It's slightly easier to do the other way than Ross.

Let $q,r$ be integers such that $a = b·c·q+r$ and $0 \le r < b·c$. Then $r \div b \le r / b < c$.

Then $( a \div b ) \div c = ( c·q + ( r \div b ) ) \div c = q + ( r \div b ) \div c = q = a \div ( b·c )$.

(We simply twice used the easy fact that $(d·x+y) \div d = x + y \div d$ for integers $x,y,d$ with $d > 0$.)

$\endgroup$
3
  • $\begingroup$ This is a nice proof; can you mention that you're using $\div$ to mean integer division? $\endgroup$ Dec 12, 2017 at 2:22
  • $\begingroup$ @ShreevatsaR: Oh, well it was defined in the question itself so I thought I didn't need to redefine it. =) $\endgroup$
    – user21820
    Dec 12, 2017 at 2:49
  • $\begingroup$ Oh I see... I read the question when it didn't have that notation, and didn't reread it afterwards :-) Now I see it, so feel free to ignore my comment. $\endgroup$ Dec 12, 2017 at 3:32
2
$\begingroup$

Another way to think about this is, say you have $N$ candies that you want to distribute among $a * b$ kids. What is the maximum number of candies a kid can get, given that you distribute the candies equally.

The answer is $\Big\lfloor\frac{N}{a*b}\Big\rfloor$

Note that you can divide the $a * b$ kids into $a$ classes. Since each student gets an equal number of candies, each class also gets an equal number of candies, which is $\le \left\lfloor\frac{N}{a}\right\rfloor$. Now for each class, you distribute these many candies among $b$ kids, so each kid gets

$$\left\lfloor\frac{\left\lfloor\frac{N}{a}\right\rfloor}{b}\right\rfloor$$

Hence,

$$\left\lfloor\frac{\left\lfloor\frac{N}{a}\right\rfloor}{b}\right\rfloor = \left\lfloor\frac{N}{a*b}\right\rfloor$$


I didn't prove that we can give $\Big\lfloor\frac{N}{a}\Big\rfloor$ candies to each class and still ensure that each student will get the optimal number of candies. This can be proven easily as well. Let's say each class gets $Y$ candies in the optimal solution. Then, we have:

$$ Y * a \le N \implies Y \le \frac{N}{a} $$

Hence we can give each class $\left\lfloor\frac{N}{a}\right\rfloor$ candies for optimal distribution.

Note that each class can also reject some candies.

$\endgroup$
0
1
$\begingroup$

$$a \text{\\} b \text{\\} c = d$$ $$\exists x.~~ a\text{\\}b = x ~~\land~~ x\text{\\}c = d$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ cd \in [x - c + 1 \dots x]$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ bcd \in [xb - bc + b \dots xb]$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ bcd \in [(a - b + 1) - bc + b \dots a]$$ $$bcd \in [a - bc + 1 \dots a]$$ $$a\text{\\}(bc) = d$$

$\endgroup$
1
  • $\begingroup$ I've deleted my previous comments because they no longer apply to the revised (completely rewritten) answer. $\endgroup$ Dec 12, 2017 at 2:19
1
$\begingroup$

This seems to work always, because it is mathematical tautology $-$ not an obvious one though. Let's denote integer division by $\div$, and say we have $(a\div b)\div c=s$. This means

$$a\div b=sc+r_c\quad\implies\quad a=(sc+r_c)b+r_b=sbc+\underbrace{r_cb+r_b}_R$$

where $r_c\in\{0,...,c-1\}$ and $r_b\in\{0,...,b-1\}$ denote the remainder after division by $c$ and $b$ respectively. We therefore have

$$R=r_cb+r_b\le b(c-1)+b-1=bc-b+b-1=bc-1<bc.$$

This suffices to conclude that

$$a\div(bc)=(sbc+R)\div(bc)=s$$

since $R$ is to small to make a difference after the division.

$\endgroup$
0
$\begingroup$

Let $\div$ denote integer division, and $/$ normal division. Let $a,b,c$ be integers and $x$ an abitrary number.

First observation:
Because we're dividing an iteger, the division $(a+x)\div b$ can only be greater than $(a\div b)$ when x is at least 1, i.e. $x\ge 1$.

Furtrher we already know that $(a/b)/c = a/(b\cdot c)$ for regular division holds.

Therefore, the only reason integer division $\div$ wouldn't hold for $(a\div b)\div c$ would be when the first division cuts off so much, the second division has an altered result.

We can now split $a$ in a divisble part $p\cdot b$ and a remainder $q$. Note that the remainder is smaller than $b$.

However, because it's a remainder, $q/b$ is smaller than 1. And because it's smaller than one, and $a\div b$ is an integer,
$(a\div b)\div c = p\div c= (p + q/b)\div c $

And therefore, the equality $(a\div b)\div c) = a\div (b\cdot c)$ holds.

$\endgroup$
2
  • $\begingroup$ (1) Unbalanced parentheses need fixing. (2) The right-hand side of the double-implication is not a statement. $\endgroup$ Dec 9, 2017 at 16:54
  • $\begingroup$ Thanks, fixed it $\endgroup$
    – Sudix
    Dec 9, 2017 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .