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$
  • 16
    $\begingroup$ Already proven in 1994. See Wikipedia. $\endgroup$ – Parcly Taxel Dec 8 '17 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 '17 at 18:27
  • 7
    $\begingroup$ I answered this on StackOverflow a few months ago. $\endgroup$ – ShreevatsaR Dec 8 '17 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$ – Ilmari Karonen Dec 8 '17 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 '17 at 20:24
46
$\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
    $\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$ – Daniel R. Collins Dec 9 '17 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$ – Ross Millikan Dec 9 '17 at 4:48
  • 3
    $\begingroup$ Yes, I know; I'm suggesting the detail be added to the answer. $\endgroup$ – Daniel R. Collins Dec 9 '17 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 '17 at 8:17
3
$\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$
  • $\begingroup$ This is a nice proof; can you mention that you're using $\div$ to mean integer division? $\endgroup$ – ShreevatsaR Dec 12 '17 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 '17 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$ – ShreevatsaR Dec 12 '17 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$
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$
  • $\begingroup$ I've deleted my previous comments because they no longer apply to the revised (completely rewritten) answer. $\endgroup$ – ShreevatsaR Dec 12 '17 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$
  • $\begingroup$ (1) Unbalanced parentheses need fixing. (2) The right-hand side of the double-implication is not a statement. $\endgroup$ – Daniel R. Collins Dec 9 '17 at 16:54
  • $\begingroup$ Thanks, fixed it $\endgroup$ – Sudix Dec 9 '17 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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