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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .