Máximo común divisor - Greatest common divisor

En matemáticas , el máximo común divisor ( MCD ) de dos o más enteros , que no son todos cero, es el mayor entero positivo que divide a cada uno de los enteros. Para dos enteros x , Y , el máximo común divisor de x y y se denota . Por ejemplo, el MCD de 8 y 12 es 4, es decir, . ${\ Displaystyle \ gcd (x, y)}$ ${\ Displaystyle \ gcd (8,12) = 4}$

En el nombre "máximo común divisor", el adjetivo "máximo" puede reemplazarse por "más alto", y la palabra "divisor" puede reemplazarse por "factor", de modo que otros nombres incluyan el máximo común divisor ( hcf ), etc. Históricamente, otros nombres para el mismo concepto han incluido la máxima medida común .

Esta noción se puede extender a polinomios (ver Máximo común divisor de polinomios ) y otros anillos conmutativos (ver § En anillos conmutativos más adelante).

Visión general

Definición

El máximo común divisor (MCD) de dos distintos de cero enteros $a$ y $b$ es el mayor número entero positivo $d$ tal que $d$ es un divisor de ambos $una$ y $b$ ; Es decir, no son números enteros $e$ y $f$ de tal manera que $un = de$ y $b = df$ , y $d$ es el más grande tal número entero. El MCD de $una$ y $b$ es generalmente denotado $gcd (a, b)$ .

Esta definición también se aplica cuando uno de $una$ y $b$ es cero. En este caso, el MCD es el valor absoluto del entero distinto de cero: $mcd (a, 0) = mcd (0, a) = | a |$ . Este caso es importante como paso final del algoritmo euclidiano .

La definición anterior no se puede utilizar para definir $mcd (0, 0)$ , ya que $0 \times n = 0$ , y por lo tanto cero no tiene mayor divisor. Sin embargo, cero es su propio divisor más grande si se entiende más grande en el contexto de la relación de divisibilidad, por lo que $gcd (0, 0)$ se define comúnmente como 0. Esto preserva las identidades habituales para GCD, y en particular la identidad de Bézout , es decir, que $gcd (a, b)$ genera el mismo ideal que ${a, b}$ . Esta convención es seguida por muchos sistemas de álgebra computacional . No obstante, algunos autores dejan indefinido el $mcd (0, 0)$ .

El MCD de $una$ y $b$ es su mayor común divisor positivo en la relación preorden de divisibilidad . Esto significa que los divisores comunes de $una$ y $b$ son exactamente los divisores de su GCD. Esto se demuestra comúnmente usando el lema de Euclides , el teorema fundamental de la aritmética o el algoritmo de Euclides . Este es el significado de "mayor" que se utiliza para las generalizaciones del concepto de GCD.

Ejemplo

El número 54 se puede expresar como un producto de dos números enteros de varias formas diferentes:

{\ Displaystyle 54 \ times 1 = 27 \ times 2 = 18 \ times 3 = 9 \ times 6.}

Por tanto, la lista completa de divisores de 54 es . Del mismo modo, los divisores de 24 son . Los números que tienen en común estas dos listas son los divisores comunes de 54 y 24, es decir, ${\ Displaystyle 1,2,3,6,9,18,27,54}$ ${\ Displaystyle 1,2,3,4,6,8,12,24}$

{\ Displaystyle 1,2,3,6.}

De estos, el mayor es 6, por lo que es el máximo común divisor :

{\ Displaystyle \ gcd (54,24) = 6.}

Calcular todos los divisores de los dos números de esta manera generalmente no es eficiente, especialmente para números grandes que tienen muchos divisores. En § Cálculo se describen métodos mucho más eficientes .

Números coprime

Dos números se denominan primos relativos, o coprimos , si su máximo común divisor es igual a 1. Por ejemplo, 9 y 28 son primos relativos.

Una vista geométrica

"Rectángulo alto y delgado dividido en una cuadrícula de cuadrados. El rectángulo tiene dos cuadrados de ancho y cinco cuadrados de alto".

Un rectángulo de 24 por 60 se cubre con diez de 12 por 12 azulejos cuadrados, donde 12 es el MCD de 24 y 60. Más en general, un una -by- b rectángulo se puede cubrir con baldosas cuadradas de longitud lateral c solamente si c es un divisor común de una y b .

Por ejemplo, un área rectangular de 24 por 60 se puede dividir en una cuadrícula de: cuadrados de 1 por 1, cuadrados de 2 por 2, cuadrados de 3 por 3, cuadrados de 4 por 4, cuadrados de 6 por -6 cuadrados o cuadrados de 12 por 12. Por lo tanto, 12 es el máximo común divisor de 24 y 60. Un área rectangular de 24 por 60 se puede dividir en una cuadrícula de 12 por 12 cuadrados, con dos cuadrados a lo largo de un borde (24/12 = 2) y cinco cuadrados a lo largo del otro (60/12 = 5).

Aplicaciones

Reducir fracciones

El máximo común divisor es útil para reducir fracciones a los términos más bajos . Por ejemplo, mcd (42, 56) = 14, por lo tanto,

{\ Displaystyle {\ frac {42} {56}} = {\ frac {3 \ cdot 14} {4 \ cdot 14}} = {\ frac {3} {4}}.}

Minimo común multiplo

El máximo común divisor se puede usar para encontrar el mínimo común múltiplo de dos números cuando se conoce el máximo común divisor, usando la relación,

{\ Displaystyle \ operatorname {lcm} (a, b) = {\ frac {| a \ cdot b |} {\ operatorname {gcd} (a, b)}}.}

Cálculo

Usando factorizaciones primas

Los divisores comunes máximos se pueden calcular determinando las factorizaciones primas de los dos números y comparando factores. Por ejemplo, para calcular el mcd (48, 180), encontramos las factorizaciones primas 48 = 2 ⁴ · 3 ¹ y 180 = 2 ² · 3 ² · 5 ¹ ; el MCD es entonces 2 ^{min (4,2)} · 3 ^{min (1,2)} · 5 ^{min (0,1)} = 2 ² · 3 ¹ · 5 ⁰ = 12, como se muestra en el diagrama de Venn . El MCM correspondiente es entonces 2 ^{max (4,2)} · 3 ^{max (1,2)} · 5 ^{max (0,1)} = 2 ⁴ · 3 ² · 5 ¹ = 720.

En la práctica, este método solo es factible para números pequeños, ya que calcular las factorizaciones primas lleva demasiado tiempo.

Algoritmo de Euclides

El método introducido por Euclides para el cálculo de máximo común divisor se basa en el hecho de que, dados dos números enteros positivos $a$ y $b$ de tal manera que $una > b$ , los divisores comunes de $una$ y $b$ son los mismos que los divisores comunes de $una - b$ y $b$ .

Entonces, el método de Euclides para calcular el máximo común divisor de dos enteros positivos consiste en reemplazar el número mayor por la diferencia de los números y repetir esto hasta que los dos números sean iguales: ese es su máximo común divisor.

Por ejemplo, para calcular el $mcd (48,18)$ , se procede de la siguiente manera:

{\ displaystyle {\ begin {alineado} (48,18) \ quad & \ to \ quad (48-18,18) = (30,18) && \ to \ quad (30-18,18) = (12, 18) \\ & \ to \ quad (12,18-12) = (12,6) && \ to \ quad (12-6,6) = (6,6). \ End {alineado}}}

Entonces $mcd (48, 18) = 6$ .

Este método puede resultar muy lento si un número es mucho mayor que el otro. Por tanto, generalmente se prefiere la variante que sigue.

Algoritmo euclidiano

Reproducir medios

Animación que muestra una aplicación del algoritmo euclidiano para encontrar el máximo común divisor de 62 y 36, que es 2.

Un método más eficiente es el algoritmo de Euclides , una variante en la que la diferencia de los dos números $a$ y $b$ se sustituye por el resto de la división euclidiana (también llamada división con resto ) de $una$ por $b$ .

Denotando este resto como $un mod b$ , el algoritmo reemplaza $(a, b)$ por $(b, a mod b)$ repetidamente hasta que el par es $(d, 0)$ , donde $d$ es el máximo común divisor.

Por ejemplo, para calcular mcd (48,18), el cálculo es el siguiente:

{\ displaystyle {\ begin {alineado} (48,18) \ quad & \ to \ quad (18,48 {\ bmod {1}} 8) = (18,12) \\ & \ to \ quad (12, 18 {\ bmod {1}} 2) = (12,6) \\ & \ to \ quad (6,12 {\ bmod {6}}) = (6,0). \ End {alineado}}}

Esto nuevamente da $mcd (48, 18) = 6$ .

Algoritmo GCD de Lehmer

El algoritmo de Lehmer se basa en la observación de que los cocientes iniciales producidos por el algoritmo de Euclid pueden determinarse basándose únicamente en los primeros dígitos; esto es útil para números que son más grandes que una palabra de computadora . En esencia, uno extrae dígitos iniciales, típicamente formando una o dos palabras de computadora, y ejecuta los algoritmos de Euclides en estos números más pequeños, siempre y cuando se garantice que los cocientes son los mismos que los que se obtendrían con los números originales. Esos cocientes se recopilan en una pequeña matriz de transformación de 2 por 2 (que es una matriz de números enteros de una sola palabra), para usarlos todos a la vez para reducir los números originales . Este proceso se repite hasta que los números son lo suficientemente pequeños como para que el algoritmo binario (ver más abajo) sea más eficiente.

Este algoritmo mejora la velocidad porque reduce el número de operaciones en números muy grandes y puede usar aritmética de hardware para la mayoría de las operaciones. De hecho, la mayoría de los cocientes son muy pequeños, por lo que una buena cantidad de pasos del algoritmo euclidiano se pueden recopilar en una matriz de 2 por 2 de números enteros de una sola palabra. Cuando el algoritmo de Lehmer encuentra un cociente que es demasiado grande, debe recurrir a una iteración del algoritmo euclidiano, con una división euclidiana de números grandes.

Algoritmo binario GCD

Los binarios utiliza el algoritmo GCD solamente resta y la división por 2. El método es como sigue: Sea una y b sean los dos no negativos números enteros. Sea 0 el entero d. Hay cinco posibilidades:

a = b .

Como gcd ( a , un ) = un , el GCD deseado es un × 2 ^d (como un y b son cambiado en los otros casos, y d registra el número de veces que una y b han sido tanto dividida por 2 en la siguiente paso, el GCD del par inicial es el producto de una y 2 ^d ).

Tanto a como b son pares.

Entonces 2 es un divisor común. Divida a y b por 2, incremente d entre 1 para registrar el número de veces que 2 es un divisor común y continúe.

a es par y b es impar.

Entonces 2 no es un divisor común. Divida a entre 2 y continúe.

a es impar y b es par.

Entonces 2 no es un divisor común. Divida b entre 2 y continúe.

Tanto a como b son impares.

Como gcd ( a , b ) = mcd ( b , una ), si un < b entonces intercambiar una y b . El número c = a - b es positivo y más pequeño que a . Cualquier número que divide a y b también deben dividir c por lo que cada común divisor de un y b es también un divisor común de b y c . Del mismo modo, un = b + c y cada común divisor de b y c es también un divisor común de una y b . Entonces, los dos pares ( a , b ) y ( b , c ) tienen los mismos divisores comunes y, por lo tanto, mcd ( a , b ) = mcd ( b , c ). Además, como a y b son impares, c es par, el proceso puede continuar con el par ( a , b ) reemplazado por los números más pequeños ( c / 2, b ) sin cambiar el MCD.

Cada uno de los pasos anteriores reduce al menos uno de un y b , dejando ellos no negativo y por lo que sólo se puede repetir un número finito de veces. Por lo tanto, finalmente, el proceso resulta en un = b , el caso de detenerse. Entonces el MCD es a × 2 ^d .

Ejemplo: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1); el MCD original es, por tanto, el producto 6 de 2 ^d = 2 ¹ y a = b = 3.

El algoritmo binario GCD es particularmente fácil de implementar en computadoras binarias. Su complejidad computacional es

{\ Displaystyle O ((\ log a + \ log b) ^ {2})}

La complejidad computacional generalmente se da en términos de la longitud $n$ de la entrada. Aquí, esta longitud es y, por lo tanto, la complejidad es ${\ Displaystyle n = \ log a + \ log b,}$

{\ Displaystyle O (n ^ {2})}

.

Otros metodos

{\ Displaystyle \ gcd (1, x) = y,}

o la función de Thomae. El sombreado en la parte inferior indica elipses (es decir, omisión de puntos debido a la densidad extremadamente alta).

Si a y b son distintos de cero, el máximo común divisor de a y b se puede calcular utilizando el mínimo común múltiplo (MCM) de a y b :

{\ Displaystyle \ gcd (a, b) = {\ frac {| a \ cdot b |} {\ operatorname {lcm} (a, b)}}}

,

pero más comúnmente, el LCM se calcula a partir del GCD.

Usando la función f de Thomae ,

{\ Displaystyle \ gcd (a, b) = af \ left ({\ frac {b} {a}} \ right),}

que generaliza a una y b números racionales o conmensurables números reales.

Keith Slavin ha demostrado que para un impar a ≥ 1:

{\ Displaystyle \ gcd (a, b) = \ log _ {2} \ prod _ {k = 0} ^ {a-1} (1 + e ^ {- 2i \ pi kb / a})}

que es una función que se puede evaluar para el complejo b . Wolfgang Schramm ha demostrado que

{\ Displaystyle \ gcd (a, b) = \ sum \ limits _ {k = 1} ^ {a} \ exp (2 \ pi ikb / a) \ cdot \ sum \ limits _ {d \ left | a \ right .} {\ frac {c_ {d} (k)} {d}}}

es una función completa en la variable b para todos los enteros positivos a donde c _d ( k ) es la suma de Ramanujan .

Complejidad

La complejidad computacional del cálculo de los máximos divisores comunes ha sido ampliamente estudiada. Si se usa el algoritmo euclidiano y los algoritmos elementales para multiplicación y división, el cálculo del máximo común divisor de dos enteros de como máximo $n$ bits es Esto significa que el cálculo del máximo común divisor tiene, hasta un factor constante, el mismo complejidad como la multiplicación. ${\ Displaystyle O (n ^ {2}).}$

Sin embargo, si se utiliza un algoritmo de multiplicación rápida , se puede modificar el algoritmo euclidiano para mejorar la complejidad, pero el cálculo del máximo común divisor se vuelve más lento que la multiplicación. Más precisamente, si la multiplicación de dos enteros de $n$ bits toma un tiempo de $T (n)$ , entonces el algoritmo más rápido conocido para el máximo común divisor tiene una complejidad Esto implica que el algoritmo más rápido conocido tiene una complejidad de ${\ Displaystyle O \ left (T (n) \ log n \ right).}$ ${\ Displaystyle O \ left (n \, (\ log n) ^ {2} \ right).}$

Complejidades anteriores son válidas para los habituales modelos de computación , específicamente multicinta máquinas de Turing y máquinas de acceso aleatorio .

El cálculo de los máximos divisores comunes pertenece, por tanto, a la clase de problemas que se pueden resolver en tiempo cuasilineal . A fortiori , el problema de decisión correspondiente pertenece a la clase P de problemas solucionables en tiempo polinomial. No se sabe que el problema de GCD esté en NC , por lo que no se conoce una forma de paralelizarlo de manera eficiente; tampoco se sabe que sea P-completo , lo que implicaría que es poco probable que sea posible paralelizar eficientemente el cálculo de GCD. Shallcross et al. mostró que un problema relacionado (EUGCD, que determina la secuencia restante que surge durante el algoritmo euclidiano) es NC-equivalente al problema de la programación lineal entera con dos variables; si cualquiera de los problemas está en NC o es P-completo , el otro también lo está. Dado que NC contiene NL , también se desconoce si existe un algoritmo de uso eficiente del espacio para calcular el GCD, incluso para máquinas de Turing no deterministas.

Aunque no se sabe que el problema esté en NC , existen algoritmos paralelos asintóticamente más rápidos que el algoritmo euclidiano; el algoritmo determinista más rápido conocido es el de Chor y Goldreich, que (en el modelo CRCW-PRAM ) puede resolver el problema en tiempo $O (n / log n)$ con procesadores $n 1 + ε$ . Los algoritmos aleatorios pueden resolver el problema en $O ((log n) 2)$ tiempo en procesadores (esto es superpolinomio ). ${\ Displaystyle \ exp \ left (O \ left ({\ sqrt {n \ log n}} \ right) \ right)}$

Propiedades

Cada común divisor de un y b es un divisor de gcd ( a , b ) .
gcd ( a , b ) , donde un y b no son ambos cero, se puede definir alternativamente y de forma equivalente como el más pequeño número entero positivo d que se puede escribir en la forma d = un ⋅ p + b ⋅ q , donde p y q son enteros. Esta expresión se llama identidad de Bézout . Números p y q esta manera se pueden calcular con el algoritmo de Euclides extendido .
mcd ( a , 0) = | a | , para a ≠ 0 , ya que cualquier número es un divisor de 0, y el mayor divisor de a es | a |. Suele utilizarse como caso base en el algoritmo euclidiano.
Si a divide el producto b ⋅ c , y mcd ( a , b ) = d , entonces a / d divide c .
Si m es un número entero no negativo, entonces mcd ( m ⋅ a , m ⋅ b ) = m ⋅gcd ( a , b ) .
Si m es un número entero, entonces mcd ( a + m ⋅ b , b ) = mcd ( a , b ) .
Si m es un divisor común positivo de un y b , entonces mcd ( un / m , b / m ) = gcd ( a , b ) / m .
La MCD es una función multiplicativa en el siguiente sentido: si a ₁ y a ₂ son primos relativos, entonces mcd ( a ₁ ⋅ a ₂ , b ) = mcd ( a ₁ , b ) ⋅gcd ( a ₂ , b ) . En particular, recordando que MCD es una función de valor entero positivo, obtenemos que mcd ( a , b ⋅ c ) = 1 si y solo si mcd ( a , b ) = 1 y mcd ( a , c ) = 1 .
La MCD es una función conmutativa : mcd ( a , b ) = mcd ( b , a ) .
La MCD es una función asociativa : mcd ( a , mcd ( b , c )) = mcd (mcd ( a , b ), c ) . Por lo tanto, gcd ( a , b , c , ...) se puede usar para denotar el MCD de múltiples argumentos.
mcd ( a , b ) está estrechamente relacionado con el mínimo común múltiplo mcm ( a , b ) : tenemos
mcd ( a , b ) ⋅lcm ( a , b ) = | a ⋅ b | .

Esta fórmula se usa a menudo para calcular los múltiplos menos comunes: primero se calcula el MCD con el algoritmo de Euclides y luego se divide el producto de los números dados por su MCD.

Las siguientes versiones de distributividad son verdaderas:

mcd ( a , mcm ( b , c )) = mcd (mcd ( a , b ), mcd ( a , c ))

mcm ( a , mcd ( b , c )) = mcd (mcm ( a , b ), mcm ( a , c )) .
Si tenemos las factorizaciones primas únicas de a = p ₁^{e ₁} p ₂^{e ₂} ⋅⋅⋅ p _m^{e _m} y b = p ₁^{f ₁} p ₂^{f ₂} ⋅⋅⋅ p _m^{f _m} donde e _i ≥ 0 y f _i ≥ 0 , entonces el GCD de una y b es
gcd ( a , b ) = p ₁^{min ( e ₁ , f ₁ )} p ₂^{min ( e ₂ , f ₂ )} ⋅⋅⋅ p _m^{min ( e _m , f _m )} .
A veces es útil definir gcd (0, 0) = 0 y lcm (0, 0) = 0 porque entonces los números naturales se convierten en una red distributiva completa con GCD como meet y LCM como operación de unión. Esta extensión de la definición también es compatible con la generalización para anillos conmutativos que se da a continuación.
En un sistema de coordenadas cartesianas , mcd ( a , b ) se puede interpretar como el número de segmentos entre puntos con coordenadas integrales en el segmento de línea recta que une los puntos (0, 0) y ( a , b ) .
Para enteros no negativos a y b , donde a y b no son ambos cero, se puede demostrar considerando el algoritmo euclidiano en base n :
gcd ( n ^un - 1, n ^b - 1) = n ^{gcd ( a , b )} - 1 .
Una identidad que involucra la función totient de Euler :
${\ Displaystyle \ gcd (a, b) = \ sum _ {k | a {\ text {y}} k | b} \ varphi (k).}$

Probabilidades y valor esperado

En 1972, James E. Nymann demostró que k números enteros, elegidos de forma independiente y uniforme de {1, ..., n }, son coprimos con probabilidad 1 / ζ ( k ) cuando n va al infinito, donde ζ se refiere a la zeta de Riemann función . (Ver coprime para una derivación). Este resultado se amplió en 1987 para mostrar que la probabilidad de que k enteros aleatorios tengan el máximo común divisor d es d ^−k / ζ ( k ).

Con esta información, se puede ver (informalmente) que el valor esperado de la función del máximo común divisor no existe cuando k = 2. En este caso, la probabilidad de que el MCD sea igual a d es d ⁻² / ζ (2), y dado que ζ (2) = π ² /6 nos tenemos

{\ Displaystyle \ mathrm {E} (\ mathrm {2}) = \ sum _ {d = 1} ^ {\ infty} d {\ frac {6} {\ pi ^ {2} d ^ {2}}} = {\ frac {6} {\ pi ^ {2}}} \ sum _ {d = 1} ^ {\ infty} {\ frac {1} {d}}.}

Esta última suma es la serie armónica , que diverge. Sin embargo, cuando k ≥ 3, el valor esperado está bien definido y, según el argumento anterior, es

{\ Displaystyle \ mathrm {E} (k) = \ sum _ {d = 1} ^ {\ infty} d ^ {1-k} \ zeta (k) ^ {- 1} = {\ frac {\ zeta ( k-1)} {\ zeta (k)}}.}

Para k = 3, esto es aproximadamente igual a 1.3684. Para k = 4, es aproximadamente 1,1106.

Si un argumento de la MCD se fija a algún valor , se convertirá en una función multiplicativa en la otra variable y se puede demostrar que ${\ Displaystyle m}$

${\ Displaystyle {\ frac {1} {N}} \ lim _ {N \ to \ infty} \ sum _ {n = 1} ^ {N} \ gcd (n, m) = \ prod _ {p ^ { \ alpha} || n} \ left (1+ \ alpha - {\ frac {\ alpha} {p}} \ right)}$

Aquí, denota el producto sobre todas las potencias primarias de modo que, pero ${\ Displaystyle \ prod _ {p ^ {\ alpha} || n}}$ ${\ Displaystyle p ^ {\ alpha}}$ ${\ Displaystyle p ^ {\ alpha} | n}$ ${\ Displaystyle p ^ {\ alpha +1} \ not | n}$

En anillos conmutativos

La noción de máximo común divisor puede definirse de manera más general para elementos de un anillo conmutativo arbitrario , aunque en general no es necesario que exista uno para cada par de elementos.

Si $R$ es un anillo conmutativo, y $una$ y $b$ están en $R$ , a continuación, un elemento $d$ de $R$ se llama un divisor común de $una$ y $b$ si se divide tanto $una$ y $b$ (es decir, si hay elementos de $x$ y $y$ en $R$ de tal manera que d · x = una y d · y = b ). Si $d$ es un divisor común de $un$ y $b$ , y cada común divisor de $un$ y $b$ divide $delta$ , entonces $d$ es llamado un máximo común divisor de $un$ y b .

Con esta definición, dos elementos de $una$ y $b$ puede muy bien tener varios divisores comunes mayores, o ninguno en absoluto. Si $R$ es un dominio de integridad , entonces cualquier dos GCD de de $una$ y $b$ debe haber elementos asociados , ya que por definición o bien hay que dividir el otro; de hecho, si existe un GCD, cualquiera de sus asociados también es un GCD. La existencia de un GCD no está asegurada en dominios integrales arbitrarios. Sin embargo, si $R$ es un dominio de factorización único , entonces cualesquiera dos elementos tienen un GCD y, de manera más general, esto es cierto en los dominios GCD . Si $R$ es un dominio euclidiano en el que la división euclidiana se da algorítmicamente (como es el caso, por ejemplo, cuando R = F [ X ] donde $F$ es un campo , o cuando $R$ es el anillo de los enteros gaussianos ), entonces los máximos divisores comunes pueden ser calculado usando una forma del algoritmo euclidiano basado en el procedimiento de división.

El siguiente es un ejemplo de un dominio integral con dos elementos que no tienen un GCD:

{\ Displaystyle R = \ mathbb {Z} \ left [{\ sqrt {-3}} \, \, \ right], \ quad a = 4 = 2 \ cdot 2 = \ left (1 + {\ sqrt {- 3}} \, \, \ right) \ left (1 - {\ sqrt {-3}} \, \, \ right), \ quad b = \ left (1 + {\ sqrt {-3}} \, \, \ derecha) \ cdot 2.}

Los elementos 2 y 1 + √ −3 son dos divisores comunes máximos (es decir, cualquier divisor común que sea múltiplo de 2 está asociado a 2, lo mismo vale para 1 + √ −3 , pero no están asociados, por lo que hay hay máximo común divisor de $un$ y b .

Correspondiente a la propiedad Bézout que puede, en cualquier anillo conmutativo, considere la colección de elementos de la forma pa + qb , donde $p$ y $q$ rango sobre el anillo. Este es el ideales generada por $una$ y $b$ , y se denota simplemente ( un , b ). En un anillo cuyos ideales son principales (un dominio ideal principal o PID), este ideal será idéntico al conjunto de múltiplos de algún elemento d del anillo ; entonces este $d$ es un máximo común divisor de $un$ y b . Pero el ideal ( un , b ) puede ser útil incluso cuando no hay un máximo común divisor de $un$ y b . (De hecho, Ernst Kummer usó este ideal como reemplazo de un MCD en su tratamiento del último teorema de Fermat , aunque lo visualizó como el conjunto de múltiplos de algún elemento $d$ del anillo hipotético o ideal , de donde proviene el término teórico del anillo).

Ver también

Notas

Referencias

Andrews, George E. (1994) [1971], Teoría de números , Dover, ISBN 9780486682525
Hardy, GH ; Wright, EM (1979), Introducción a la teoría de los números (Quinta ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
Long, Calvin T. (1972), Introducción elemental a la teoría de números (2a ed.), Lexington: DC Heath and Company , LCCN 77171950
Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Elementos de la teoría de números , Englewood Cliffs: Prentice Hall , LCCN 71081766

Otras lecturas

Donald Knuth . El arte de la programación informática , volumen 2: algoritmos seminuméricos , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Sección 4.5.2: El mayor divisor común, págs. 333–356.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 31.2: Máximo común divisor, págs. 856–862.
Saunders Mac Lane y Garrett Birkhoff . Una encuesta de álgebra moderna , cuarta edición. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2 . 1-7: "El algoritmo euclidiano".

Languages

In other projects