# Proof for $\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$

Problem: For positive integers $n,j,k$, prove that the following holds:

$$\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$$

I simply need hints to start on this problem. I have verified that it's indeed true by checking a few examples and I can't seem to find a counter-example, so I'm almost sure that the problem is indeed correct.

However, I can't seem to think of a proper (and rigorous) proof of this. Can someone please help me by giving me a few hints?

I want to prove it myself, so I'd appreciate if people don't directly post the proof themselves. Also, please keep your hints as subtle as possible (there's no fun in proving something if the hint gives out most of the answer) :D

• A proof that a = b can be achieved by showing that a <= b and b <= a. Or, given that they are integers, it is sufficient to show that b - 1 < a <= b. – Maciek Jun 25 '15 at 7:48

Hint: Let $n=kl+r$, where $l,r\in\mathbb{N}, 0\leqslant r<k$. Then $$\left\lfloor\frac n{k}\right\rfloor=l$$ Let $l=jp+q$, where $p,q\in\mathbb{N}, 0\leqslant q<j$ again and plug it in above.

Suppose $l=jp+q$, where $p,q\in\mathbb{N}, 0\leqslant q<j$. Then $$n=kjp+kq+r$$

where $0\leqslant kq+r<k(q+1)\leqslant kj$.

So $$\left\lfloor\frac n{jk}\right\rfloor=p=\left\lfloor\dfrac{l}{j}\right\rfloor=\left\lfloor\dfrac{1}{j}\left\lfloor\dfrac{n}{k}\right\rfloor\right\rfloor$$

Hint:

Such problems are solved by means of the division theorem. It states that when you divide two integers, you get a unique quotient and a unique remainder such that the following two relations hold:

$$a = b\cdot q+r,$$ $$0\le r<b.$$

Using this tool, you can show that the result of the division of $n$ by $k$, then by $j$ is the same as the result of the direct division of $n$ by $jk$.

Solution:

Divide by $k$:

$$n=kq+r,0\le r<k.$$

Divide the result by $j$:

$$q=jq'+r',0\le r'<j.$$

Combine:

$$n=jkq'+kr'+r,0\le kr'+r<(j-1)k+k=jk.$$

Compare to:

$$n=(jk)q''+r'',0\le r''<jk.$$

You can use this obvious fact: $\left\lfloor\frac{n}{k}\right\rfloor=\max\{c\in\mathbb{N}:kc\le n\}$.

Below is the complete solution (put the mouse over the box to see it):

$$\left\lfloor \frac{1}{j} \left\lfloor \frac{n}{k} \right\rfloor \right\rfloor=\left\lfloor \frac{1}{j}\max\{b\in\mathbb{N}:kb\le n\} \right\rfloor=\max\{a\in\mathbb{N}:ja\le\max\{b\in\mathbb{N}:kb\le n\}\}$$ $$=\max\{a\in\mathbb{N}:k(ja)\le n\}=\left\lfloor\frac{n}{jk}\right\rfloor$$ where the second to last equality holds since $b'\le\max\{b\in\mathbb{N}:kb\le n\}$ iff $kb'\le n$ (choose $b':=ja$).