A number theory exercise involving the floor function

251 Views Asked by At

The problem is to prove that for integers $a,b$ with $b > 0$ $$\left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor = \left\lfloor \frac{a}{b^2} \right\rfloor.$$

I did this by obtaining an inequality both ways. First $$k = \left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor \leq \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \leq \frac{a}{b^2}. $$ Since $k$ is an integer,$$\left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor \leq \left\lfloor \frac{a}{b^2} \right\rfloor.$$ Then $$\left\lfloor \frac{a}{b^2} \right\rfloor = \left\lfloor \frac{nb^2 +r}{b^2} \right\rfloor,$$ with $0 \leq r < b^2$ an integer. $$k' = \left\lfloor \frac{nb^2 +r}{b^2} \right\rfloor = n = \frac{1}{b} \left\lfloor nb \right\rfloor \leq \frac{1}{b} \left\lfloor nb + \frac{r}{b} \right\rfloor = \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor.$$ Since $k'$ is an integer $$\left\lfloor \frac{a}{b^2} \right\rfloor \leq \left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor $$ and we are done.

This is the first problem of the course and considering that, this solution feels insanely difficult. Is there an easier way to do this?

1

There are 1 best solutions below

0
On BEST ANSWER

Is there an easier way to do this?

How about the following way?

There exist integers $m,r$ such that $$a=bm+r\quad\text{and}\quad 0\le r\lt b$$ from which $$bm\le bm+r\lt b+bm\implies \frac mb\le \frac{bm+r}{b^2}\lt \frac{m+1}{b}$$ follows.

Since there is no integer $n$ such that $$\frac mb\lt n\lt \frac{m+1}{b}$$ we get $$\left\lfloor\frac{a}{b^2}\right\rfloor=\left\lfloor\frac{bm+r}{b^2}\right\rfloor=\left\lfloor\frac mb\right\rfloor=\left\lfloor\frac 1b\left\lfloor\frac ab\right\rfloor\right\rfloor$$