Proving $\Big\lfloor{x}/({y}\cdot{z})\Big\rfloor=\Big\lfloor{\lfloor{x}/{y}\rfloor}/{z}\Big\rfloor$ for positive integers

Question

I want to prove that the following identity is true for any positive integers $x,y,z$:

$$\Big\lfloor{x}/({y}\cdot{z})\Big\rfloor=\Big\lfloor{\lfloor{x}/{y}\rfloor}/{z}\Big\rfloor$$

Here is a script that I wrote in Python 3 to test it:

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            print(x, y, z)
            assert x // (y * z) == x // y // z

So empirically it seems to hold, but I'm finding it hard to establish a formal proof.

Any idea?

Answer 1

$$\begin{array}{rc} & \left\lfloor \dfrac {\lfloor x/y \rfloor} z \right\rfloor = u \\ \iff& uz \le \lfloor x/y \rfloor < (u+1)z \\ \iff& uz \le \lfloor x/y \rfloor \le (u+1)z-1 \\ \iff& uyz \le x < ((u+1)z-1+1)y \\ \iff& uyz \le x < (u+1)yz \\ \iff& \left\lfloor \dfrac x {yz} \right\rfloor = u \\ \end{array}$$

Answer 2

Write $x=ayz+r$ where $r<yz$. Then $\lfloor x/(y\cdot z)\rfloor=a$, so we just need to check the right hand side is also equal to $a$. Then, using repeatedly that $\lfloor n+m\rfloor=\lfloor n\rfloor+\lfloor m\rfloor$ whenever $n$ is an integer, we can write:

$$\big\lfloor\lfloor (ayz+r)/y\rfloor/z\big\rfloor=\big\lfloor(az+\lfloor r/y\rfloor)/z\big\rfloor=a+\big\lfloor\lfloor r/y\rfloor/z\big\rfloor$$

$r<yz$ now implies that $\lfloor r/y\rfloor\leq r/y<z$, so $\lfloor r/y\rfloor/z<1$ and we conclude that the right hand side is equal to $a$.

Answer 3

Sure. You may write

(1) $x = ky + r$, $0 \le r < y$

And then

(2) $k = qz + s$, $0 \le s < z$

Both of these are simply ordinary integer division with remainder. Now $\lfloor x/y \rfloor = k$ and $\lfloor k/z \rfloor = q$, so $\lfloor \lfloor x/y\rfloor /z\rfloor = q$.

On the other hand, substituting (2) in (1) you find

$x = (qz+s)y+r = qzy + sy + r$

and $sy + r \le (z-1)y + r < (z-1)y + y = zy$

and so $sy+r$ is indeed the remainder when dividing $x$ by $zy$, so

$\lfloor x/(zy)\rfloor =q$ as well, QED.