Proving $\left\lfloor \frac{x}{ab} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{x}{a} \right\rfloor}{b} \right\rfloor$ for $a,b>1$

Question

I'm trying to prove rigorously the following:

$$\left\lfloor \frac{x}{ab} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{x}{a} \right\rfloor}{b} \right\rfloor$$ for integers $a,b \geq 1$ and real $x$.

So far I haven't gotten far. It's enough to prove this instead:

$$\left\lfloor \frac{z}{c} \right\rfloor = \left\lfloor \frac{\lfloor z \rfloor}{c} \right\rfloor$$ for integers $c \geq 1$ and real $z$

since we can just put $z=\lfloor x/a \rfloor$ and $c=b$.

Answer 1

Let $\lfloor x/a \rfloor$ = c(say)=>x=ca+d 0≤d

Let $\lfloor c/b \rfloor$=e(say)=>c=be+f 0≤f

=>x=ca+d=(be+f)a+d=abe+af+d.

$\frac{x}{a}$=be+f+ $\frac{d}{a}$

$\frac{\frac{x}{a}}{b}$=e+$\frac{f}{b}$+$\frac{d}{ab}$

=>$\lfloor x/a/b \rfloor$ = e = $\lfloor c/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$

Answer 2

This theorem is not true if $b$ is not an integer. Take $x=b=1.5$ and take $a=1$.

If $b$ is an integer, this follows from the rule $$\left\lfloor \frac{y}{b}\right\rfloor = \left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor$$

Setting $y=\frac x a$.

Showing this rule, then, suffices.

Let $y = \lfloor y \rfloor + \{y\}$, where $0\leq \{y\} < 1$.

Use division algorithm to write $\lfloor y \rfloor = qb + r$ with $0\leq r <b$.

The $\frac{\lfloor y \rfloor} b = q + \frac{r}{b}$, and $0\leq \frac{r}{b} <1$, so

$$\left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor = q$$

On the other hand, since $[y]< (q+1)b$, since $0\leq\{y\}<1$, then $y = [y]+\{y\}<(q+1)b$.

So $q \leq \frac y b < q+1$ and again $$\left\lfloor \frac{y}{b}\right\rfloor = q $$

Answer 3

It is trivial when done universally, i.e. using the universal definition of floor

$\begin{align} k\,&\le\, \lfloor x\rfloor \color{#c00}{\iff} k\,\le\, x,\quad {\rm for\ all}\,\ k\in\Bbb Z\\[1em] {\bf Lemma}\qquad\quad\color{#0a0}{\lfloor r/n\rfloor}\,& =\, \lfloor{\lfloor r\rfloor}/n\rfloor\ \ {\rm for}\ \ 0<n\in\Bbb Z,\,\ r\in\Bbb R\\[.6em] {\bf Proof}\qquad\qquad\quad\ \ \ k \,&\le \lfloor{\lfloor r\rfloor}/n\rfloor\\[.4em] \color{#c00}\iff\quad k\ & \le\ \:{\lfloor r\rfloor}/n\\[.2em] \overset{\times\, n}\iff\ \ nk\ &\le\ \ \lfloor r\rfloor\qquad {\rm by}\,\ n>0\\[.4em] \color{#c00}\iff\ \ nk\ &\le\,\ \ \ r\qquad\ \ {\rm by}\,\ n\in\Bbb Z\\[.2em] \overset{\div\,n}\iff\ \ \ \ k\ &\le\:\ \ \ r/n\quad\ {\rm by}\,\ n>0\\[.4em] \color{#c00}\iff\ \ \ \ k\ &\le\ \ \color{#0a0}{\lfloor r/n\rfloor}\quad {\small\bf QED} \end{align}$

Yours is special case $\ r = x/a,\,\ n = b.$

Re: universality: see the links in comments below for more general (category-theoretic) viewpoints.