Máximo común divisor

El entero más grande que divide a los enteros dados

En matemáticas , el máximo común divisor ( MCD ), también conocido como máximo común divisor (MCD), de dos o más números enteros , que no sean todos cero, es el mayor entero positivo que divide a cada uno de los números enteros. Para dos números enteros x , y , el máximo común divisor de x e y se denota como . Por ejemplo, el MCD de 8 y 12 es 4, es decir, mcd(8, 12) = 4. [ ^{1] [2]} ${\displaystyle \gcd(x,y)}$

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 incluyen máximo común divisor , etc. ^{[3] [4] [5] [6]} Históricamente, otros nombres para el mismo concepto han incluido máximo común medida . ^[7]

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

Descripción general

Definición

El máximo común divisor (MCD) de los números enteros a y b , de los cuales al menos uno es distinto de cero, es el mayor número entero positivo d tal que d sea divisor tanto de a como de b ; es decir, hay números enteros e y f tales que a = de y b = df , y d es el mayor de dichos números enteros. El MCD de a y b se denota generalmente como mcd( a , b ) . ^[8]

Cuando uno de a y b es cero, el MCD es el valor absoluto del entero distinto de cero: mcd( a , 0) = mcd(0, a ) = | a | . Este caso es importante porque es el paso final del algoritmo euclidiano.

La definición anterior no es adecuada para definir mcd(0, 0) , ya que no existe un entero máximo n tal que 0 × n = 0 . Sin embargo, cero es su propio máximo divisor si se entiende máximo en el contexto de la relación de divisibilidad, por lo que mcd(0, 0) se define comúnmente como 0 . Esto preserva las identidades habituales para mcd, y en particular la identidad de Bézout , a saber, que mcd( a , b ) genera el mismo ideal que { a , b } . ^{[9] [10] [11]} Esta convención es seguida por muchos sistemas de álgebra computacional . ^[12] No obstante, algunos autores dejan mcd(0, 0) sin definir. ^[13]

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

Ejemplo

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

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

Así, la lista completa de divisores de 54 es 1, 2, 3, 6, 9, 18, 27, 54. De manera similar, los divisores de 24 son 1, 2, 3, 4, 6, 8, 12, 24. Los números que estas dos listas tienen en común son los divisores comunes de 54 y 24, es decir,

${\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 dos números de esta manera no suele ser eficiente, especialmente para números grandes que tienen muchos divisores. En § Cálculo se describen métodos mucho más eficientes .

Números coprimos

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

Una visión geométrica

Un rectángulo de 24 por 60 se cubre con diez baldosas cuadradas de 12 por 12, donde 12 es el MCD de 24 y 60. De manera más general, un rectángulo de a por b se puede cubrir con baldosas cuadradas de lado c solo si c es un divisor común de a 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 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 cuadrados de 12 por 12, con dos cuadrados a lo largo de un borde ( 24/12 = 2 ) y cinco cuadrados a lo largo del otro ( 60/12 = 5 ).

Aplicaciones

Reducción de fracciones

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

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

Mínimo común múltiplo

El mínimo común múltiplo de dos números enteros que no sean ambos cero se puede calcular a partir de su máximo común divisor, utilizando la relación

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

Cálculo

Uso de factorizaciones primas

Los máximos comunes divisores se pueden calcular determinando las factorizaciones primas de los dos números y comparando los factores. Por ejemplo, para calcular 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 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 sólo es viable para números pequeños, ya que calcular factorizaciones primas lleva demasiado tiempo.

Algoritmo de Euclides

El método introducido por Euclides para calcular el máximo común divisor se basa en el hecho de que, dados dos números enteros positivos a y b tales que a > b , los divisores comunes de a y b son los mismos que los divisores comunes de a – b y b .

Entonces, el método de Euclides para calcular el máximo común divisor de dos números enteros positivos consiste en reemplazar el número mayor con 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 mcd(48,18) , se procede de la siguiente manera:

${\displaystyle {\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)\\&\to \quad \gcd(30-18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)\\&\to \quad \gcd(12-6,6)=\gcd(6,6).\end{aligned}}}$

Entonces mcd(48, 18) = 6 .

Este método puede resultar muy lento si un número es mucho mayor que el otro, por lo que generalmente se prefiere la variante que se indica a continuación.

Algoritmo euclidiano

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 euclidiano , 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 a por b .

Al denotar este resto como a módulo b , el algoritmo reemplaza ( a , b ) con ( b , a módulo b ) repetidamente hasta que el par sea ( 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{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd(6,0).\end{aligned}}}$

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

Algoritmo MCD binario

El algoritmo binario MCD es una variante del algoritmo de Euclides especialmente adaptada a la representación binaria de los números, que se utiliza en la mayoría de los ordenadores .

El algoritmo binario MCD se diferencia del algoritmo de Euclides esencialmente en que divide por dos cada número par que se encuentra durante el cálculo. Su eficiencia resulta del hecho de que, en la representación binaria, la prueba de paridad consiste en probar el dígito más a la derecha, y la división por dos consiste en eliminar el dígito más a la derecha.

El método es el siguiente, comenzando con a y b que son los dos números enteros positivos cuyo MCD se busca.

1. Si a y b son ambos pares, entonces divida ambos por dos hasta que al menos uno de ellos sea impar; sea d el número de estas divisiones pareadas.
2. Si a es par, entonces divídelo por dos hasta que sea impar.
3. Si b es par, entonces divídelo por dos hasta que sea impar.

   Ahora, a y b son impares y seguirán siendo impares hasta el final del cálculo.

4. Mientras que a ≠ b lo haga
   • Si a > b , entonces reemplace a con a – b y divida el resultado por dos hasta que a se vuelva impar (como a y b son impares, hay al menos una división por 2).
   • Si a < b , entonces reemplace b con b – a y divida el resultado por dos hasta que b se vuelva impar.
5. Ahora, a = b , y el máximo común divisor es ${\displaystyle 2^{d}a.}$

El paso 1 determina que d es la potencia más alta de 2 que divide a y b y, por lo tanto, su máximo común divisor. Ninguno de los pasos cambia el conjunto de los divisores comunes impares de a y b . Esto demuestra que cuando el algoritmo se detiene, el resultado es correcto. El algoritmo se detiene eventualmente, ya que cada paso divide al menos uno de los operandos por al menos 2. Además, el número de divisiones por 2 y, por lo tanto, el número de restas es, como máximo, el número total de dígitos.

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 entonces el producto 6 de 2 ^d = 2 ¹ y a = b = 3 .

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

${\displaystyle O((\log a+\log b)^{2}).}$

El cuadrado de esta complejidad proviene del hecho de que la división por 2 y la resta toman un tiempo proporcional al número de bits de la entrada.

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

${\displaystyle O(n^{2})}$.

Algoritmo MCD de Lehmer

El algoritmo de Lehmer se basa en la observación de que los cocientes iniciales producidos por el algoritmo de Euclides se pueden determinar 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, se extraen los dígitos iniciales, que normalmente forman una o dos palabras de computadora, y se ejecutan los algoritmos de Euclides en estos números más pequeños, siempre que se garantice que los cocientes sean los mismos que los que se obtendrían con los números originales. Los cocientes se recopilan en una pequeña matriz de transformación de 2 por 2 (una matriz de números enteros de una sola palabra) para reducir los números originales. Este proceso se repite hasta que los números sean lo suficientemente pequeños como para que el algoritmo binario (ver a continuación) sea más eficiente.

Este algoritmo mejora la velocidad, ya que reduce el número de operaciones con números muy grandes y puede utilizar 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 se puede recopilar una buena cantidad de pasos del algoritmo euclidiano en una matriz de 2 por 2 de números enteros de una sola palabra. Cuando el algoritmo de Lehmer encuentra un cociente demasiado grande, debe recurrir a una iteración del algoritmo euclidiano, con una división euclidiana de números grandes.

Otros métodos

${\displaystyle \gcd(1,x)=y,}$o función de Thomae. El rayado en la parte inferior indica elipses (es decir, omisión de puntos debido a la densidad extremadamente alta).

Si a y b son ambos 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 MCM se calcula a partir del MCD.

Usando la función f de Thomae ,

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

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

Keith Slavin ha demostrado que para un número impar ≥ 1 :

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

que es una función que puede evaluarse para el complejo b . ^[16] 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 entera en la variable b para todos los enteros positivos a donde c _d ( k ) es la suma de Ramanujan . ^[17]

Complejidad

La complejidad computacional del cálculo de máximos comunes divisores ha sido ampliamente estudiada. ^[18] Si se utiliza el algoritmo euclidiano y los algoritmos elementales de multiplicación y división, el cálculo del máximo común divisor de dos números enteros de como máximo n bits es O ( n ² ) . Esto significa que el cálculo del máximo común divisor tiene, hasta un factor constante, la misma complejidad que la multiplicación.

Sin embargo, si se utiliza un algoritmo de multiplicación rápido, se puede modificar el algoritmo euclidiano para mejorar la complejidad, pero el cálculo de un máximo común divisor se vuelve más lento que la multiplicación. Más precisamente, si la multiplicación de dos números 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 O ( T ( n ) log n ) . Esto implica que el algoritmo más rápido conocido tiene una complejidad de O ( n (log n ) ² ) .

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

El cálculo de los máximos comunes divisores pertenece, por tanto, a la clase de problemas resolubles en tiempo cuasilineal . A fortiori , el problema de decisión correspondiente pertenece a la clase P de problemas resolubles en tiempo polinomial. No se sabe que el problema de MCD esté en NC , por lo que no hay ninguna forma conocida de paralelizarlo de manera eficiente; ni se sabe que sea P-completo , lo que implicaría que es poco probable que sea posible paralelizar de manera eficiente el cálculo de MCD. Shallcross et al. demostraron que un problema relacionado (EUGCD, que determina la secuencia de restos que surge durante el algoritmo euclidiano) es NC-equivalente al problema de programación lineal entera con dos variables; si cualquiera de los problemas está en NC o es P-completo , el otro también lo es. ^[19] Dado que NC contiene NL , también se desconoce si existe un algoritmo eficiente en el espacio para calcular el MCD, 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+ ε} . ^[20] Los algoritmos aleatorios pueden resolver el problema en tiempo O ((log n ) ² ) en procesadores ^{[ aclaración necesaria ]} (esto es superpolinomial ). ^[21] ${\displaystyle \exp \left(O\left({\sqrt {n\log n}}\right)\right)}$

Propiedades

• Para números enteros positivos a , mcd( a , a ) = a .
• Todo divisor común de a y b es un divisor de mcd( a , b ) .
• El mcd( a , b ) , donde a y b no son ambos cero, se puede definir de forma alternativa y equivalente como el entero positivo más pequeño d que se puede escribir en la forma d = a ⋅ p + b ⋅ q , donde p y q son números enteros. Esta expresión se denomina identidad de Bézout . Los números p y q como este se pueden calcular con el algoritmo euclidiano extendido .
• mcd( a , 0) = | a | , para a ≠ 0 , ya que cualquier número es divisor de 0, y el mayor divisor de a es | a | . ^{[2] [5]} Este 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 a c .
• Si m es un entero positivo, entonces mcd( m ⋅ a , m ⋅ b ) = m ⋅mcd( a , b ) .
• Si m es cualquier entero, entonces mcd( a + m ⋅ b , b ) = mcd( a , b ) . De manera equivalente, mcd( a mod b , b ) = mcd( a , b ) .
• Si m es un divisor común positivo de a y b , entonces mcd( a / m , b / m ) = mcd( a , b )/ m .
• El MCD es una función conmutativa : mcd( a , b ) = mcd( b , a ) .
• El MCD es una función asociativa : mcd( a , mcd( b , c )) = mcd(mcd( a , b ), c ​​) . Por lo tanto, mcd( a , b , c , ...) se puede utilizar para indicar el MCD de múltiples argumentos.
• El MCD es una función multiplicativa en el siguiente sentido: si a ₁ y a ₂ son primos entre sí, entonces mcd( a ₁ ⋅ a ₂ , b ) = mcd( a ₁ , b )⋅mcd( a ₂ , b ) .
• mcd( a , b ) está estrechamente relacionado con el mínimo común múltiplo mcm( a , b ) : tenemos

  mcd( a , b )⋅mcm( a , b ) = | a ⋅ b | .

Esta fórmula se utiliza a menudo para calcular los mínimos comunes múltiplos: 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 válidas:

  mcd( a , mcm( b , c )) = mcm(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 MCD de a y b es

  mcd( a , b ) = p 1 min( e 1 , f 1 ) p 2 min ( e 2 , f 2 ) ⋅⋅⋅ pm min( em , f m ) .

• A veces es útil definir mcd(0, 0) = 0 y mcm(0, 0) = 0 porque entonces los números naturales se convierten en una red distributiva completa con MCD como operación de intersección y MCM como operación de unión. ^[22] 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 números enteros no negativos a y b , donde a y b no son ambos cero, demostrable considerando el algoritmo euclidiano en base  n : ^[23]

  mcd( n ^a − 1, n ^b − 1) = n ^{mcd( a , b )} − 1 .

• Una identidad que involucra la función totiente de Euler :

  ${\displaystyle \gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).}$

• Función sumatoria del MCD (función aritmética de Pillai):

${\displaystyle \sum _{k=1}^{n}\gcd(k,n)=\sum _{d|n}d\phi \left({\frac {n}{d}}\right)=n\sum _{d|n}{\frac {\varphi (d)}{d}}=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)}$donde es la valoración p -ádica. (secuencia A018804 en la OEIS ) ${\displaystyle \nu _{p}(n)}$

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 tiende a infinito, donde ζ se refiere a la función zeta de Riemann . ^[24] (Ver coprimos para una derivación). Este resultado se amplió en 1987 para mostrar que la probabilidad de que k números enteros aleatorios tengan el máximo común divisor d es d ^{− k} /ζ( k ) . ^[25]

Con esta información, se puede ver (informalmente) que el valor esperado de la función 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 como ζ (2) = π ² /6 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, por 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.

En anillos conmutativos

La noción de máximo común divisor se puede definir de forma más general para los elementos de un anillo conmutativo arbitrario , aunque en general no es necesario que exista uno para cada par de elementos. ^[26]

• Si R es un anillo conmutativo, y a y b están en R , entonces un elemento d de R se llama divisor común de a y b si divide tanto a a como b (es decir, si hay elementos x e y en R tales que d · x  =  a y d · y  =  b ).
• Si d es un divisor común de a y b , y todo divisor común de a y b divide a d , entonces d se llama máximo común divisor de a y b .

Con esta definición, dos elementos a y b pueden tener varios máximos comunes divisores, o ninguno. Si R es un dominio entero , entonces dos MCD cualesquiera de a y b deben ser elementos asociados , ya que por definición cualquiera de ellos debe dividir al otro. De hecho, si existe un MCD, cualquiera de sus asociados también es un MCD.

La existencia de un MCD no está asegurada en dominios integrales arbitrarios. Sin embargo, si R es un dominio de factorización única o cualquier otro dominio de MCD , entonces dos elementos cualesquiera tienen un MCD. 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 cuerpo , o cuando R es el anillo de números enteros gaussianos ), entonces los máximos comunes divisores se pueden calcular utilizando una forma del algoritmo euclidiano basada en el procedimiento de división.

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

${\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}}\,\,\right)\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 no existe un máximo común divisor de a y  b) .

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

Véase también

• Dominio Bézout
• Mínimo común denominador
• Divisor unitario

Notas

1. Long (1972, pág. 33)
2. Pettofrezzo y Byrkit (1970, pág. 34)
3. Kelley, W. Michael (2004). Guía completa para idiotas del álgebra. Penguin. pág. 142. ISBN 978-1-59257-161-1..
4. Jones, Allyn (1999). Números enteros, decimales, porcentajes y fracciones, año 7. Pascal Press. pág. 16. ISBN 978-1-86441-378-6..
5. Hardy y Wright (1979, pág. 20)
6. Algunos autores tratanmáximo común denominador como sinónimo demáximo común divisor. Esto contradice el significado común de las palabras que se utilizan, ya que denominador se refiere afracciones, y dos fracciones no tienen ningún máximo común denominador (si dos fracciones tienen el mismo denominador, se obtiene un mayor común denominador al multiplicar todos los numeradores y denominadores por el mismonúmero entero).
7. Barlow, Peter ; Peacock, George ; Lardner, Dionisio ; Airy, Sir George Biddell ; Hamilton, HP ; Levy, A.; De Morgan, Augustus ; Mosley, Henry (1847). Enciclopedia de matemáticas puras. R. Griffin and Co. pág. 589..
8. Algunos autores utilizan ( a , b ) , ^{[1] [2] [5]} pero esta notación es a menudo ambigua. Andrews (1994, p. 16) lo explica así: "Muchos autores escriben ( a , b ) en lugar de mcd( a , b ) . Nosotros no lo hacemos, porque a menudo utilizaremos ( a , b ) para representar un punto en el plano euclidiano".
9. Thomas H. Cormen, et al. , Introducción a los algoritmos (2.ª edición, 2001) ISBN 0262032937 , pág. 852 
10. Bernard L. Johnston, Fred Richman, Números y simetría: una introducción al álgebra ISBN 084930301X , pág. 38 
11. Martyn R. Dixon, et al. , Introducción a las estructuras algebraicas esenciales ISBN 1118497759 , pág. 59 
12. p. ej., cálculo de Wolfram Alpha y Maxima
13. Jonathan Katz, Yehuda Lindell, Introducción a la criptografía moderna ISBN 1351133012 , 2020, sección 9.1.1, pág. 45 
14. Weisstein, Eric W. "Máximo común divisor". mathworld.wolfram.com . Consultado el 30 de agosto de 2020 .
15. "Máximo común divisor". www.mathsisfun.com . Consultado el 30 de agosto de 2020 .
16. Slavin, Keith R. (2008). "Q-Binomiales y el máximo común divisor". INTEGERS : The Electronic Journal of Combinatorial Number Theory . 8. Universidad de West Georgia , Universidad Charles de Praga : A5 . Consultado el 26 de mayo de 2008 .
17. Schramm, Wolfgang (2008). "La transformada de Fourier de funciones del máximo común divisor". INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8. Universidad de Georgia Occidental , Universidad Charles de Praga : A50 . Consultado el 25 de noviembre de 2008 .
18. Knuth, Donald E. (1997). El arte de la programación informática . Vol. 2: Algoritmos seminuméricos (3.ª ed.). Addison-Wesley Professional. ISBN 0-201-89684-2.
19. Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "La equivalencia NC de la programación lineal entera planar y el MCD euclidiano" (PDF) . 34.° Simposio IEEE sobre fundamentos de la informática . págs. 557–564. Archivado (PDF) desde el original el 5 de septiembre de 2006.
20. Chor, B. ; Goldreich, O. (1990). "Un algoritmo paralelo mejorado para MCD entero". Algorithmica . 5 (1–4): 1–10. doi :10.1007/BF01840374. S2CID  17699330.
21. Adleman, LM; Kompella, K. (1988). "Uso de la suavidad para lograr paralelismo". 20.º Simposio anual de la ACM sobre teoría de la computación . Nueva York. pp. 528–538. doi :10.1145/62212.62264. ISBN. 0-89791-264-0.S2CID 9118047  .
22. Müller-Hoissen, Folkert; Walther, Hans-Otto (2012). "Dov Tamari (antes Bernhard Teitler)". En Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim (eds.). Associahedra, Tamari Lattices y estructuras relacionadas: Tamari Memorial Festschrift . Progreso en Matemáticas. vol. 299. Birkhäuser. págs. 1–40. ISBN 978-3-0348-0405-9.Nota 27, p. 9: "Por ejemplo, los números naturales con mcd (máximo común divisor) como resultado y mcm (mínimo común múltiplo) como operación de unión determinan una red (distributiva completa)". Para obtener este resultado es necesario incluir estas definiciones para el 0: si, en cambio, se omite el 0 del conjunto de números naturales, la red resultante no es completa.
23. Knuth, Donald E .; Graham, RL; Patashnik, O. (marzo de 1994). Matemáticas concretas: una base para la informática . Addison-Wesley . ISBN 0-201-55802-5.
24. Nymann, JE (1972). "Sobre la probabilidad de que k enteros positivos sean primos entre sí". Journal of Number Theory . 4 (5): 469–473. Bibcode :1972JNT.....4..469N. doi : 10.1016/0022-314X(72)90038-8 .
25. Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "Sobre la probabilidad de que los valores de m polinomios tengan un mcd dado" Journal of Number Theory . 26 (3): 237–245. doi : 10.1016/0022-314X(87)90081-3 .
26. Lovett, Stephen (2015). "Divisibilidad en anillos conmutativos". Álgebra abstracta: estructuras y aplicaciones . Boca Raton: CRC Press. pp. 267–318. ISBN 9781482248913.

Referencias

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

Lectura adicional

• 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 máximo común divisor, 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 . A Survey of Modern Algebra , cuarta edición. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2 . 1–7: "El algoritmo euclidiano".