El cociente de la división euclidiana.

Question

$\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$ $

Tengo que demostrar que

$$ \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} $$

¿Podría alguien darme algunos consejos sobre cómo probar eso sin usar la inducción?

Answer 1

Prueba de $\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}$

Tenga en cuenta que $\bigg\lfloor\frac{[x]}{m}\bigg\rfloor=\bigg\lfloor\frac{x}{m}\bigg\rfloor$ al $m$ es entero positivo, como en este caso. Por qué? Debido a $x=\lfloor x \rfloor+f$ algunos $0\leq f<1$, lo que significa $\bigg\lfloor\frac{x}{m}\bigg\rfloor=\bigg\lfloor\frac{[x]}{m}+\frac{f}{m}\bigg\rfloor$ y desde $\frac{f}{m}$ es positivo y menor que 1, es igual a $\bigg\lfloor\frac{[x]}{m}\bigg\rfloor$. Reemplace $x$ $\bigg\lfloor\frac{n}{\prod_{i=1}^{k-1}a_i}\bigg\rfloor$ $m$ $a_k$ y listo.

---

Prueba de $2:$

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

A partir de la declaración de $n=q_1a_1+r_1~;~ 0 \leq r_1 < a_1$ , obtenemos que $\bigg\lfloor\frac{n}{a_1}\bigg\rfloor=\bigg\lfloor q_1+\frac{r_1}{a_1}\bigg\rfloor$. Desde $\frac{r_1}{a_1} < 1,$ $\bigg\lfloor\frac{n}{a_1}\bigg\rfloor=q_1$ Ahora, por los mismos argumentos, $\bigg\lfloor\frac{q_1}{a_2}\bigg\rfloor=q_2$. A partir de lo que ha demostrado en la primera parte (Prueba 1), obtenemos $\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$. Proceder de esta manera para obtener $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

Answer 2

Como premisa que tenemos $$ \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} $$ donde los corchetes indican la Iverson soporte.

Entonces podemos escribir $$ \eqalign{ y 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} $$

ya definitivamente $$ \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\} $$

Por tanto, la vuelta hasta $q_{0}=n$ consigue $$ q_{\,k} = \left\lfloor {{n \over {a_{\,1} \cdots a_{\,k - 1} a_{\,k} }}} \right\rfloor $$

y la segunda parte de la siguiente manera.