How can I show the equality,when a does not divide n?

[evinda]

Hello! (Wave)

I want to show that:

$$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor }{b} \rfloor = \lfloor \frac{n}{ab} \rfloor$$

That's what I have tried:

$$\lfloor \frac{n}{a} \rfloor =\max \{ m \in \mathbb{Z}: m \leq \frac{n}{a}\}$$

• $a \mid n:$
  $$\lfloor \frac{n}{a} \rfloor=\frac{n}{a}$$
  
  Then:
  
  $$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor }{b} \rfloor = \lfloor \frac{\frac{n}{a}}{b}\rfloor =\lfloor \frac{n}{ab} \rfloor $$
  
• $a \nmid n:$
  $$\lfloor \frac{n}{a} \rfloor=\frac{n-k}{a},0<k\leq n$$
  $$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor }{b} \rfloor= \lfloor \frac{n-k}{ab}\rfloor= \max \{ m \in \mathbb{Z}: m \leq \frac{n-k}{ab}\} (*) $$

But..to show what the exercise asks,I have to show that $(*)$ is equal to $\max \{ m \in \mathbb{Z}: m \leq \frac{n}{ab}\}$.

How can I do this? (Thinking)(Thinking)

 

[I like Serena]

• $a \nmid n:$
  $$\lfloor \frac{n}{a} \rfloor=\frac{n-k}{a},0<k\leq n$$
  $$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor }{b} \rfloor= \lfloor \frac{n-k}{ab}\rfloor= \max \{ m \in \mathbb{Z}: m \leq \frac{n-k}{ab}\} (*) $$

But..to show what the exercise asks,I have to show that $(*)$ is equal to $\max \{ m \in \mathbb{Z}: m \leq \frac{n}{ab}\}$.

How can I do this? (Thinking)(Thinking)

Hi! ;)

Suppose we pick $q$ and $r$ such that:
$$n=qab + r$$
with
$$0 \le r < ab$$

Then:
$$q=\left\lfloor \frac{n}{ab} \right\rfloor$$
and:
$$0 \le \frac ra < b$$

It follows that:
$$\left\lfloor \frac{ \left\lfloor \frac{n}{a} \right\rfloor}{b}\right\rfloor
= \left\lfloor \frac{ \left\lfloor \frac{qab + r}{a} \right\rfloor}{b}\right\rfloor
= \left\lfloor \frac{ qb + \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor
= q + \left\lfloor \frac{ \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor
= q
$$

In other words:
$$\left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \frac{ \left\lfloor \frac{n}{a} \right\rfloor}{b}\right\rfloor$$
(Mmm)

 

[Deveno]

Just a thought:

If $n = qa + r$ with $0 \leq r < a$

then:

$\lfloor \frac{n}{a}\rfloor = \lfloor q + \frac{r}{a}\rfloor = q$

since $0 \leq \dfrac{r}{a} < 1$

Repeating, we have:

$q = q'b + r'$, so that:

$\lfloor \frac{q}{b}\rfloor = \lfloor q' + \frac{r,}{b}\rfloor = q'$

Now $n = qa + r = (q'b + r')a + r = (q')(ab) + ar' + r$

So now all you have to do is show that:

$ar' + r < ab$.

 

[evinda]

Hi! ;)

Suppose we pick $q$ and $r$ such that:
$$n=qab + r$$
with
$$0 \le r < ab$$

Then:
$$q=\left\lfloor \frac{n}{ab} \right\rfloor$$
and:
$$0 \le \frac ra < b$$

It follows that:
$$\left\lfloor \frac{ \left\lfloor \frac{n}{a} \right\rfloor}{b}\right\rfloor
= \left\lfloor \frac{ \left\lfloor \frac{qab + r}{a} \right\rfloor}{b}\right\rfloor
= \left\lfloor \frac{ qb + \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor
= q + \left\lfloor \frac{ \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor
= q
$$

In other words:
$$\left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \frac{ \left\lfloor \frac{n}{a} \right\rfloor}{b}\right\rfloor$$
(Mmm)

How did you get from this: $\displaystyle{ \left\lfloor \frac{ \left\lfloor \frac{qab + r}{a} \right\rfloor}{b}\right\rfloor }$ to this one: $ \displaystyle{ \left\lfloor \frac{ qb + \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor } $?

 

[I like Serena]

How did you get from this: $\displaystyle{ \left\lfloor \frac{ \left\lfloor \frac{qab + r}{a} \right\rfloor}{b}\right\rfloor }$ to this one: $ \displaystyle{ \left\lfloor \frac{ qb + \left\lfloor \frac{r}{a} \right\rfloor}{b}\right\rfloor } $?

We have:
$$
\left\lfloor \frac{qab + r}{a} \right\rfloor
=\left\lfloor qb + \frac{r}{a} \right\rfloor
$$
Since $qb$ is an integer, it does not affect the rounding, so we can take it out of the floor operation.
So:
$$\left\lfloor qb + \frac{r}{a} \right\rfloor
=qb + \left\lfloor \frac{r}{a} \right\rfloor
$$

 

[evinda]

Just a thought:

If $n = qa + r$ with $0 \leq r < a$

then:

$\lfloor \frac{n}{a}\rfloor = \lfloor q + \frac{r}{a}\rfloor = q$

since $0 \leq \dfrac{r}{a} < 1$

Repeating, we have:

$q = q'b + r'$, so that:

$\lfloor \frac{q}{b}\rfloor = \lfloor q' + \frac{r,}{b}\rfloor = q'$

Now $n = qa + r = (q'b + r')a + r = (q')(ab) + ar' + r$

I understood so far..

So now all you have to do is show that:

$ar' + r < ab$.

But..why do I have to show now that $ar' + r < ab$ ? Could you explain it further to me? (Thinking)

 

[evinda]

We have:
$$
\left\lfloor \frac{qab + r}{a} \right\rfloor
=\left\lfloor qb + \frac{r}{a} \right\rfloor
$$
Since $qb$ is an integer, it does not affect the rounding, so we can take it out of the floor operation.
So:
$$\left\lfloor qb + \frac{r}{a} \right\rfloor
=qb + \left\lfloor \frac{r}{a} \right\rfloor
$$

A ok! I understand.. (Happy) And also,why is it: $\displaystyle{ q+ \frac{ \lfloor \frac{r}{a} \rfloor }{b}}=q$ ? Has it to do with the fact that: $\displaystyle{ \frac{r}{a}<b}$ ? (Thinking)

 

[I like Serena]

A ok! I understand.. (Happy) And also,why is it: $\displaystyle{ q+ \frac{ \lfloor \frac{r}{a} \rfloor }{b}}=q$ ? Has it to do with the fact that: $\displaystyle{ \frac{r}{a}<b}$ ? (Thinking)

That should be:
$${ q+ \left\lfloor\frac{ \lfloor \frac{r}{a} \rfloor }{b}\right\rfloor}=q$$
And yes, when we divide a numerator by a greater denominator and round down, the result is zero.

 

[Deveno]

We have:
$$
\left\lfloor \frac{qab + r}{a} \right\rfloor
=\left\lfloor qb + \frac{r}{a} \right\rfloor
$$
Since $qb$ is an integer, it does not affect the rounding, so we can take it out of the floor operation.

This is true, but depending on "what is taken as given" it may need justification.

In other words, there should be a lemma/theorem somewhere that:

If $k \in \Bbb Z$, then for any $x \in \Bbb R$, we have:

$\lfloor x+ k\rfloor = \lfloor x \rfloor + k$.

I presented what I did in two stages, for this reason-

At each stage, when I was evaluating an expression:

$\left\lfloor \dfrac{qa+r}{a} \right\rfloor$

I wanted the "remainder fraction" to be clearly between 0 and 1, so that the floor of:

$\dfrac{qa+r}{a}$ was clearly $q$.

Now, from what I posted before, we have:

$\left\lfloor \dfrac{\lfloor\frac{n}{a}\rfloor}{b} \right\rfloor = \lfloor \frac{q}{b}\rfloor = q'$

If we have that $0 \leq ar' + r < ab$, we have:

$0 \leq \dfrac{ar' + r}{ab} < 1$, which means that:

$\left\lfloor \dfrac{n}{ab} \right\rfloor = \left\lfloor q' + \dfrac{ar' + r}{ab}\right\rfloor = q'$, as well, so the two are equal.

It's not hard to show that $0 \leq ar' + r < b$:

We certainly have, from $r' < b$ that $r' \leq b - 1$, so that $ar' \leq a(b - 1) = ab - a$.

We also have $r < a$, so:

$ar' + r \leq ab - a + r < ab - a + a = ab$.

**********************

In all fairness, this is what ILS's equation:

$0 \leq \dfrac{r}{a} < b$ also accomplishes, for that means:

$0 \leq \dfrac{r}{ab} < \dfrac{b}{b} = 1$.

 

[evinda]

That should be:
$${ q+ \left\lfloor\frac{ \lfloor \frac{r}{a} \rfloor }{b}\right\rfloor}=q$$
And yes, when we divide a numerator by a greater denominator and round down, the result is zero.

Oh yes,right! (Nod) So,can we say that $\frac{r}{a}<b \Rightarrow \lfloor \frac{r}{a} \rfloor <b$ ? (Thinking)

Also,doing it like that:

$$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor}{b} \rfloor=\lfloor \frac{ \lfloor \frac{qab+r}{a} \rfloor}{b} \rfloor, \text{ with } 0 \leq r<ab$$
both of the cases $a \mid n$ and $a \nmid n$ are included,so we don't have to take cases,right? (Thinking)

 

[I like Serena]

Oh yes,right! (Nod) So,can we say that $\frac{r}{a}<b \Rightarrow \lfloor \frac{r}{a} \rfloor <b$ ? (Thinking)

Yep. We can do it like that! (Happy)
More specifically:
$$\left\lfloor \frac{r}{a} \right\rfloor \le \frac{r}{a}$$

Also,doing it like that:

$$\lfloor \frac{ \lfloor \frac{n}{a} \rfloor}{b} \rfloor=\lfloor \frac{ \lfloor \frac{qab+r}{a} \rfloor}{b} \rfloor, \text{ with } 0 \leq r<ab$$
both of the cases $a \mid n$ and $a \nmid n$ are included,so we don't have to take cases,right? (Thinking)

Yep. We're covering both cases all at once. (Mmm)

 

[evinda]

Yep. We can do it like that! (Happy)
More specifically:
$$\left\lfloor \frac{r}{a} \right\rfloor \le \frac{r}{a}$$

Yep. We're covering both cases all at once. (Mmm)

I understand! Thank you very much! (Cool)