Los números en la pizarra

Question

Hay una lista de $N$ números naturales en la pizarra. En un paso que usted puede escoger cualquier número dos, que no se divide cada uno de los otros. En lugar de esta pares de escribir su mcd y mcm. Problema pregunta para demostrar que el resultado final no depende del orden en que esta operación se aplica. Supongo que para demostrar que la operación es asociativa.

$$(4, 6, 9) \rightarrow\ (2, 12, 9) \rightarrow \ (2, 3, 36) \rightarrow \ (1, 6, 36)$$

$$(4, 6, 9)\ \rightarrow\ (4, 3, 18)\ \rightarrow\ (1, 12, 18) \rightarrow\ (1, 6, 36)$$

Me imagino que en la cabeza y la cola de final de la lista de resultados contiene mcd y la pantalla lcd de la totalidad de la lista. Sin embargo, lo que va entre que yo no.

Answer 1

Las operaciones de $\gcd$ $\def\lcm{\operatorname{lcm}}\lcm$ puede ser representado como el de las operaciones de $\min$$\max$, respectivamente, en los exponentes en el primer factorizations:

$$ \gcd\left(\prod_ip_i^{a_i},\prod_ip_i^{b_i}\right)=\prod_ip_i^{\min(a_i,b_i)}\;,\\ \lcm\left(\prod_ip_i^{a_i},\prod_ip_i^{b_i}\right)=\prod_ip_i^{\max(a_i,b_i)}\;. $$

Cuando se aplica $\gcd$ $\lcm$ a dos números, para cada uno de los prime poner el menor exponente en la $\gcd$ y el mayor exponente de la $\lcm$. Usted todavía tiene el mismo exponentes; que acaban de llegar se clasifican en mayores y menores. Mediante la definición de una adecuada ordenación de medida, por ejemplo, $\left|\sum_i(a_i-b_i)\right|$ registrado durante todos los pares de números, y señalando que se incrementa en cada paso y está delimitada desde arriba, se puede mostrar que el proceso termina. Es evidente que sólo puede terminar si el total del pedido ha sido alcanzado, donde por dos pares uno contiene todo al menor de los exponentes y el otro todos los mayores exponentes. De ello se desprende que cuando los números están dispuestos en este orden, los exponentes de cada una de las prime están dispuestos también en este orden. Esto determina los exponentes, y por lo tanto los números, y de ello se sigue que la terminal de estado es independiente de la orden de las operaciones.

Gracias a Carl por lo que sugiere este enfoque.

P. S.: Para hacer esto un poco más concreto, podemos representar los números $4,6,9$ en su ejemplo, por sus exponentes de las dos primos $2$ $3$ que se producen en ellos. A continuación, comenzamos con $(2,0)$, $(1,1)$ y $(0,2)$. Clasificación de los exponentes en el primer componente de rendimientos $0,1,2$, y lo mismo para el segundo componente, por lo que la terminal de los vectores de $(0,0)$, $(1,1)$ y $(2,2)$, correspondiente a $1,6,36$.

Answer 2

Limpio problema. No tengo una solución completa, pero creo que un área productiva podría ser el primer factorizations de los números y ver lo que sucede a los exponentes.

$$(2^2\cdot3^0, 2^1\cdot3^1, 2^0\cdot 3^2)$$

$$\to (2^1\cdot3^0, 2^2\cdot 3^1, 2^0\cdot3^2) \to (2^1\cdot3^0, 2^0\cdot3^1, 2^2\cdot 3^2) \to$$

o

$$\to(2^2\cdot3^0, 2^0\cdot3^1, 2^1\cdot3^2) \to(2^0\cdot3^0, 2^2\cdot 3^1, 2^1\cdot3^2) \to$$

$$(2^0\cdot3^0, 2^1\cdot3^1, 2^2\cdot 3^2)$$

En el primer caso, las potencias de 2 son $(2^2,2^1,2^0)$, que se transforma en $(2^1,2^2,2^0)$ y, a continuación, $(2^1,2^0,2^2)$ antes de terminar como $(2^0,2^1,2^2)$. En el segundo caso $(2^2,2^1,2^0)$ hace $(2^2,2^0,2^1)$ y, a continuación, $(2^0,2^2,2^1)$ antes de terminar como $(2^0,2^1,2^2)$. Los exponentes parecen ser la clasificación de sí mismos. Lo mismo sucede con las potencias de 3, y pasaría a los poderes de cualquier otro de los números primos.

(Lo siento, esto no es una evidencia completa, pero parece que podría conducir a una).

Answer 3

Tenga en cuenta que en la configuración al final, para cada par de números del uno es el mínimo común múltiplo de los dos y el otro es el máximo común divisor (de lo contrario se obtiene una lista diferente). Por lo que el mayor es un múltiplo entero de la parte inferior.

Organizar los números en orden ascendente - te $d, a_1d, a_1a_2d \dots$

Ahora observe que si se le cae el primer elemento (o de la última, de hecho o de cualquiera de ellos) de la misma propiedad se mantiene. Soltar $d$ y la brecha a través de por $d$. A continuación, $a_1$ es el hcf de lo que queda (etc).

Answer 4

Como usted dice, usted está demostrando que la $f: \langle x,y \rangle \mapsto \langle \text{gcd}(x,y), \text{lcm}(x, y) \rangle$ es asociativa.

Voy a escribir $g: \mathbb{N}^n \to \mathbb{N}$ para el MCD de la función, y $l: \mathbb{N}^n \to \mathbb{N}$ de la LCM, utilizando el útil convención de $g(a,b,c)$ $g(g(a,b),c)$ etc - justificada por el párrafo siguiente.

Yo la primera reclamación que $g$ es asociativa. De hecho, eso es obvio, sólo considerando el primer factorisations de las entradas. Asimismo,$l$, aunque se puede demostrar mediante el uso de $l(x, y) = \frac{x y}{g(x, y)}$.

Ahora, yo reclamo que $g(l(x, y), z) = l(g(x,z), g(y, z))$. Este nuevo sigue considerando el primer factorisations.

Por lo tanto, es posible en cualquier expresión de la forma "secuencia de LCMs y GCDs" para sacar todo el MCM de los términos en la parte delantera. Por otra parte, la expresión resultante es, precisamente, de la forma $l( g(a,b,\dots), g(c,d,\dots), \dots)$ sin más niveles de anidamiento. Sólo tenemos que demostrar que la estructura es la misma, sin embargo nos aplicar las operaciones.

En tu ejemplo, {4, 6, 9}, nos encontramos con {g(4, 6), l(4, 6), 9}, {g(4, 6), g(l(4, 6), 9), l(l(4, 6), 9)} que es $$\{g(4, 6), l(g(4, 9), g(6, 9)), l(4, 6, 9)\}$$

Finalmente, $\{g(g(4,6), l(g(4,9),g(6,9))), l(g(4,6), l(g(4,9),g(6,9))), l(4,6,9)\}$ $$\{g(4, 6, 9), l(g(4,6), g(4,9), g(6,9)), l(4,6,9)\}$$

Este es claramente simétrica, por lo que no se puede importar el orden tomamos las operaciones en llegar.

Yo no confiar en ninguna de las propiedades especiales de los 4, 6, 9: están en general $a, b, c$. Es claro, por el camino, que debemos detener el procedimiento aquí, porque $g(a,b,c)$ divide $l(g(a,b),g(b,c),g(a,c))$ que se divide $l(a,b,c)$.

Esto se generaliza, messily, por inducción.

Answer 5

La operación no cambia el producto de los números. Desde que he descubierto lo que dos de los números de el resultado final será, puede resolver para el restante.