Motivación de la definición de GCD y LCM

Question

Según yo, puedo encontrar el GCD de dos enteros (digamos $a$ y $b$ ) encontrando todos los factores comunes de ellos, y luego encontrando el máximo de todos estos factores comunes. Esto también justifica la terminología máximo común divisor .

Sin embargo, la definición general utilizada es que $d$ se dice que es un GCD de $a$ y $b$ si

1. $d$ divide ambos $a$ y $b$ y,
2. Si $d'$ también divide a ambos $a$ y $b$ entonces $d'$ divide $d$ .

Mi pregunta es por qué solemos aceptar la segunda definición en lugar de la primera. A mí la primera me parece muy intuitiva y sencilla, y hace justicia a la terminología. La misma pregunta es válida también para LCM.

Espero su respuesta. Gracias.

Answer 1

En los dominios euclidianos, como $\mathbb Z$ y $\rm\:F[x],\:$ el gcd se define a menudo como un divisor común que es "mayor" según la valoración euclidiana, aquí $\rm\:|n|\:$ y $\rm\:deg\ f(x)\:$ Pero los dominios integrales generales pueden no venir equipados con dicha estructura, por lo que en esta atmósfera más enrarecida uno se ve obligado a confiar sólo en la propia relación de divisibilidad para especificar la propiedad de extremidad apropiada. En concreto, se emplea lo siguiente universal definiciones duales de LCM y GCD

Definición de LCM $\quad$ Si $\quad\rm a,b\mid c \iff [a,b]\mid c \quad$ entonces $\,\quad\rm [a,b] \;$ es un LCM de $\:\rm a,b$

Definición de GCD $\quad$ Si $\quad\rm c\mid a,b \iff c\mid (a,b) \quad$ entonces $\quad\rm (a,b) \;$ es un GCD de $\:\rm a,b$

Aviso $\rm\,(a,b)\mid a,b\,$ por la dirección $(\Rightarrow)$ para $\rm\,c=(a,b),\,$ es decir $\rm\,(a,b)\,$ es un común divisor de $\rm\,a,b.\,$ Dirección inversa $(\Leftarrow)$ implica $\rm\,(a,b)\,$ es divisible por cualquier divisor común $\,\rm c\,$ de $\rm\,a,b\,$ por lo tanto $\rm\,(a,b)$ es un común divisor "mayor" en el orden (parcial) dado por la divisibilidad. Del mismo modo, dualmente, la definición de lcm lo especifica como un común múltiplo que es "menor" en el orden de divisibilidad.

Se puede comprobar fácilmente que esta definición universal es equivalente a las nociones más específicas empleadas en los dominios euclidianos como $\,\Bbb Z\,$ y $\rm\,F[x].$

Estas definiciones universales permiten a menudo dar una respuesta rápida. bidireccional pruebas que unifican de forma concisa las dos direcciones de las flechas, por ejemplo, considere la siguiente prueba de la lcm fundamental $*$ ley gcd.

Teorema $\rm\;\; (a,b) = ab/[a,b] \;\;$ si $\;\rm\ [a,b] \;$ existe.

Prueba $\ \ \ \rm d\mid (a,b)\iff d\:|\:a,b \iff a,b\:|\:ab/d \iff [a,b]\:|\:ab/d \iff d\:|\:ab/[a,b] $

Muchas propiedades de los dominios son puramente multiplicativas, por lo que pueden describirse en términos de estructura monoide. Sea R un dominio con campo de fracción K. Sean R* y K* los grupos multiplicativos de unidades de R y K respectivamente. Entonces G(R), el grupo de divisibilidad de R, es el grupo de factores K*/R*.

• R es un UFD $\iff$ G(R) $\:\rm\cong \mathbb Z^{\:I}\:$ es una suma de copias de $\rm\:\mathbb Z\:.$

• R es un dominio gcd $\iff$ G(R) está ordenado en celosía (existe lub{x,y})

• R es un dominio de valoración $\iff$ G(R) está ordenada linealmente

• R es un dominio de Riesz $\iff$ G(R) es un grupo de Riesz, es decir un grupo ordenado que satisface la propiedad de interpolación de Riesz: si $\rm\:a,b \le c,d\:$ entonces $\rm\:a,b \le x \le c,d\:$ para algunos $\rm\:x\:.\:$ Un dominio $\rm\:R\:$ es Riesz si cada elemento es primario, es decir $\rm\:A\:|\:BC\ \Rightarrow\ A = bc,\ b\:|\:B,\ c\:|\:C,\:$ para algunos $\rm b,c\in R.$

Para más información sobre los grupos de divisibilidad, consulte las siguientes encuestas:

J.L. Mott. Grupos de divisibilidad: Un concepto unificador para dominios integrales y grupos parcialmente ordenados, Mathematics and its Applications, no. 48, 1989, pp. 80-104.

J.L. Mott. El grupo de divisibilidad y sus aplicaciones, Conference on Commutative Algebra (Univ. Kansas, Lawrence, Kan, 1972), Springer, Berlín, 1973, pp. 194-208. Lecture Notes in Math, Vol. 311. MR 49 #2712

Answer 2

La motivación proviene de la generalización de la definición a anillos más abstractos (técnicamente, dominios integrales).

El GCD de dos elementos $a$ y $b$ es efectivamente un elemento mayor del conjunto $S$ de los divisores comunes de $a$ y $b$ . Sin embargo, el giro radica en la forma de interpretar el calificativo "mayor". Como señala J.M., muchos anillos de interés no admiten un orden lineal interesante, por lo que no está inmediatamente claro cuál es el "mayor elemento" de un conjunto $S$ podría significar.

Sin embargo, no hay que rendirse. En nuestro contexto, parece natural dotar al anillo de un preordenar inducido por la divisibilidad: $x \preccurlyeq y$ si y sólo si $x$ divide $y$ . [De hecho, se puede pretender que $\preccurlyeq$ es un pedido parcial mediante el cociente de las unidades del anillo]. Al principio, esto parece un poco insatisfactorio porque esta relación es parcial es decir, no todos los pares de elementos (por ejemplo $42$ y $72$ ) son comparables a través de la divisibilidad. Sin embargo, esto resulta ser lo correcto para estudiar.

Armados con este preorden, podemos definir un GCD de $a$ y $b$ para ser cualquier elemento mayor del conjunto $S$ de todos los divisores comunes de $a$ y $b$ . Se puede comprobar que esto no es más que una reformulación de la segunda definición de la pregunta.

Una vez motivada la definición, debo advertirle de un par de advertencias:

• Ciertamente, no es el caso de que todos los anillos tengan definidos los CGD para todos los pares de elementos. Sin embargo, hay muchos interesantes que sí los tienen: por ejemplo, se pueden calcular GCDs de enteros, de enteros gaussianos, de polinomios, etc.

• Haciéndonos eco de la observación de GEdgar, para el caso especial de los enteros positivos, tenemos ahora dos definiciones de GCD que compiten entre sí, dependiendo del significado de "mayor". Afortunadamente, resulta que estas dos definiciones coinciden y, por tanto, podemos utilizar cualquiera de ellas según nos convenga.

Answer 3

Por dos razones:

1) Puedes calcular el GCD y el LCM sin saber nada sobre números primos y factorización de primos.

2) ¿Cuál es el GCD de 13121341 y 234132431?

La factorización de primos no puede ayudarte aquí, el problema de la factorización de primos es bastante difícil incluso para los ordenadores. En realidad, la mayor parte de la seguridad de Internet se basa en el hecho de que no hay ningún algoritmo conocido para factorizar números grandes en un tiempo razonable.

Puedes calcular este GCD utilizando el Algoritmo Euclidiano, que se puede demostrar fácilmente utilizando la segunda definición, y no tiene nada que ver con la factorización de primos.

Creo que la segunda razón suele ser la principal...

Answer 4

En realidad, tiene usted razón, salvo en un caso.

$\gcd(0,0) = 0$

Los divisores de $0$ son $D_0 = \{0, \pm 1, \pm 2, \dots \}$ y no hay ningún elemento mayor de este conjunto. Pero claramente $d'|0$ y $d'|0 \implies d'|0$ . Así que $\gcd(0,0) = 0$ .

Lo que la segunda definición capta que la primera no capta es que $D_m \cap D_n = D_{\gcd(m,n)}$ donde $D_x$ representa el conjunto de todos los divisores de $x$ . En palabras, se encuentra el conjunto de todos los divisores de $m,$ el conjunto de todos los divisores de $n,$ y luego encontrar el conjunto de todos los números que esos dos conjuntos tienen en común. ese conjunto es el conjunto de todos los divisores de $\gcd(m,n)$ .