5
$\begingroup$

$\text{Let } n,\ a_1,\ a_2, \ldots, \ a_n \text{ be natural numbers, such that:} $

$$n = q_1a_1 + r_1, 0\le r_1<a_1$$ $$q_1 = q_2a_2 + r_2, 0\le r_2<a_2$$ $$\vdots$$ $$q_{k-1} = q_ka_k + r_k, 0\le r_k<a_k$$

I have to prove that

$$\begin{cases} \hfill q_k = \left\lfloor\frac{n}{\prod_{i=1}^{k} a_i}\right\rfloor \\ \hfill \left\lfloor \frac{n}{\prod_{i=1}^{k} a_i} \right\rfloor = \left\lfloor\frac{\left\lfloor\frac{n}{\prod_{i=1}^{k-1} a_i}\right\rfloor}{a_k}\right\rfloor\\ \end{cases}$$

Could someone give me some hints how to prove that without using induction?

$\endgroup$

2 Answers 2

3
$\begingroup$

Proof $\mathbb{1}:$

$\boxed{\left\lfloor \frac{n}{\prod_{i=1}^{k} a_i} \right\rfloor = \left\lfloor\frac{\left\lfloor\frac{n}{\prod_{i=1}^{k-1} a_i}\right\rfloor}{a_k}\right\rfloor}$

Note that $\bigg\lfloor\frac{[x]}{m}\bigg\rfloor=\bigg\lfloor\frac{x}{m}\bigg\rfloor$ when $m$ is positive integer as in this case. Why? Because $x=\lfloor x \rfloor+f$ for some $0\leq f<1$ which means $\bigg\lfloor\frac{x}{m}\bigg\rfloor=\bigg\lfloor\frac{[x]}{m}+\frac{f}{m}\bigg\rfloor$ and since $\frac{f}{m}$ is positive and less than 1, it equals $\bigg\lfloor\frac{[x]}{m}\bigg\rfloor$. Replace $x$ with $\bigg\lfloor\frac{n}{\prod_{i=1}^{k-1}a_i}\bigg\rfloor$ and $m$ with $a_k$ and be done.


Proof $2:$

$\boxed{q_k=\Bigg\lfloor\frac{n}{\prod_{i=1}^{k}a_i}\Bigg\rfloor}$

From the statement $n=q_1a_1+r_1~;~ 0 \leq r_1 < a_1$ , we get that $\bigg\lfloor\frac{n}{a_1}\bigg\rfloor=\bigg\lfloor q_1+\frac{r_1}{a_1}\bigg\rfloor$. Since $\frac{r_1}{a_1} < 1,$ $\bigg\lfloor\frac{n}{a_1}\bigg\rfloor=q_1$ Now see, by the same arguments, $\bigg\lfloor\frac{q_1}{a_2}\bigg\rfloor=q_2$. From what we did prove in the first part (Proof 1), we get $\bigg\lfloor\frac{q_1}{a_2}\bigg\rfloor=\Bigg\lfloor\frac{\bigg\lfloor\frac{n}{a_1}\bigg\rfloor}{a_2}\Bigg\rfloor=\bigg\lfloor\frac{n}{a_1a_2}\bigg\rfloor$. Proceed in this manner to get $q_k=\Bigg\lfloor\frac{n}{a_1a_2a_3 \cdots a_k}\Bigg\rfloor=\Bigg\lfloor\frac{n}{\prod_{i=1}^{k}a_i}\Bigg\rfloor$

Q.E.D

$\endgroup$
2
$\begingroup$

Premised that we have $$ \eqalign{ & \left\lfloor {x - y} \right\rfloor = \left\lfloor {\left\lfloor x \right\rfloor - \left\lfloor y \right\rfloor + \left\{ x \right\} - \left\{ y \right\}} \right\rfloor = \cr & = \left\lfloor x \right\rfloor - \left\lfloor y \right\rfloor + \left\lfloor {\left\{ x \right\} - \left\{ y \right\}} \right\rfloor = \cr & = \left\lfloor x \right\rfloor - \left\lfloor y \right\rfloor - \left[ {\left\{ x \right\} < \left\{ y \right\}} \right] \cr} $$ where the square bracket denote the Iverson bracket.

Then we can write $$ \eqalign{ & q_{\,k} = \left\lfloor {{{q_{\,k - 1} } \over {a_{\,k} }}} \right\rfloor = \left\lfloor {{{\left\lfloor {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\rfloor } \over {a_{\,k} }}} \right\rfloor = \left\lfloor {{{{{q_{\,k - 2} } \over {a_{\,k - 1} }} - \left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \over {a_{\,k} }}} \right\rfloor = \cr & = \left\lfloor {{{q_{\,k - 2} } \over {a_{\,k - 1} a_{\,k} }} - {1 \over {a_{\,k} }}\left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \right\rfloor = \cr & = \left\lfloor {{{q_{\,k - 2} } \over {a_{\,k - 1} a_{\,k} }}} \right\rfloor - \left\lfloor {{1 \over {a_{\,k} }}\left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \right\rfloor + \left\lfloor {\left\{ {{1 \over {a_{\,k} }}{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\} - \left\{ {{1 \over {a_{\,k} }}\left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \right\}} \right\rfloor = \cr & = \left\lfloor {{{q_{\,k - 2} } \over {a_{\,k - 1} a_{\,k} }}} \right\rfloor \cr} $$

since definitely $$ \left\{ {{1 \over {a_{\,k} }}{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\} = \left\{ {{{\left\lfloor {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\rfloor + \left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \over {a_{\,k} }}} \right\} \ge \left\{ {{1 \over {a_{\,k} }}\left\{ {{{q_{\,k - 2} } \over {a_{\,k - 1} }}} \right\}} \right\} $$

So, going back till $q_{0}=n$ you get $$ q_{\,k} = \left\lfloor {{n \over {a_{\,1} \cdots a_{\,k - 1} a_{\,k} }}} \right\rfloor $$

and the second part follows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.