Máximo común divisor

En matemáticas , el máximo común divisor ( MCD ), también conocido como máximo factor común (MCF) , 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$ $e$ y se denota como $\gcd(x,y)$ Por ejemplo, el MCD de 8 y 12 es 4, es decir, $mcd(8, 12) =$ 4. ^{[ 1 ]}^{[ 2 ]}

En el nombre "máximo común divisor", el adjetivo "mayor" puede reemplazarse por "máximo", y la palabra "divisor" puede reemplazarse por "factor", de modo que otros nombres incluyen máximo común divisor (MCD) , etc. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}^{[ 6 ]} Históricamente, otros nombres para el mismo concepto han incluido máximo común medida . ^{[ 7 ]}

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

Descripción general

Definición

El máximo común divisor (MCD) de los enteros $a$ y $b$ , de los cuales al menos uno es distinto de cero, es el mayor entero positivo $d$ tal que $d$ es divisor tanto de $a$ como $de b$ ; es decir, existen enteros $e$ y $f$ tales que $a = de$ y $b = df$ , y $d$ es el mayor de estos 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 como paso final del algoritmo euclidiano .

La definición anterior no es adecuada para definir $mcd(0, 0)$ , ya que no existe un entero mayor $n$ tal que $0 \times n = 0.$ Sin embargo, cero es su propio divisor mayor si se entiende "mayor" en el contexto de la relación de divisibilidad, por lo que $mcd(0, 0)$ se define comúnmente como $0.$ Esto conserva 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 máximo común divisor (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 suele demostrar mediante el lema de Euclides , el teorema fundamental de la aritmética o el algoritmo euclidiano . 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:

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,

1,2,3,6.

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

\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 la sección Cálculo se describen métodos mucho más eficientes .

números coprimos

Dos números se denominan primos relativos, 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

"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 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 así 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

Fracciones reductoras

El máximo común divisor es útil para reducir fracciones a su mínima expresión . ^{[ 15 ]} Por ejemplo, $mcd(42, 56) = 14$ , por lo tanto,

{\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 enteros que no son ambos cero se puede calcular a partir de su máximo común divisor, utilizando la relación

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

Cálculo

Utilizando factorizaciones primas

El máximo común divisor se puede 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 solo es viable para números pequeños, ya que calcular las factorizaciones primas lleva demasiado tiempo.

El 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 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$ .

Así pues, el método de Euclides para calcular el máximo común divisor de dos enteros positivos consiste en sustituir el número mayor por la diferencia entre ambos y repetir este proceso hasta que los dos números sean iguales: ese es su máximo común divisor.

Por ejemplo, para calcular $el máximo común divisor (mcd) de 48 y 18$ , se procede de la siguiente manera:

{\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 ser muy lento si un número es mucho mayor que el otro. Por lo tanto, generalmente se prefiere la siguiente variante.

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 reemplaza por el resto de la división euclidiana (también llamada división con resto ) de $a$ por $b$ .

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

Por ejemplo, para calcular el máximo común divisor (mcd) de 48 y 18, el cálculo es el siguiente:

{\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 $mcd(48, 18) = 6$ .

Algoritmo binario de MCD

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

El algoritmo del máximo común divisor binario 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 se debe a que, en la representación binaria, comprobar la paridad consiste en comprobar el dígito más a la derecha, y dividir por dos consiste en eliminar dicho dígito.

El método es el siguiente, comenzando con $a$ y $b$ que son los dos enteros positivos cuyo máximo común divisor se busca.

Si $a$ y $b$ son ambos pares, entonces divídalos ambos por dos hasta que al menos uno de ellos sea impar; sea $d$ el número de estas divisiones por pares.
Si $a$ es par, divídelo entre dos hasta que sea impar.
Si $b$ es par, divídelo entre dos hasta que sea impar.
Ahora bien, tanto $a$ como $b$ son impares y seguirán siéndolo hasta el final del cálculo.
Mientras a ≠ b hacer
- Si $a > b$ , entonces reemplaza $a$ con $a - b$ y divide el resultado por dos hasta que $a$ sea impar (como $a$ y $b$ son ambos impares, hay, al menos, una división por 2).
- Si $a < b$ , entonces reemplaza $b$ con $b - a$ y divide el resultado por dos hasta que $b$ sea impar.
Ahora, $a = b$ , y el máximo común divisor es $2^{d}a.$

El paso 1 determina que $d$ es la mayor potencia de $2$ que divide $a$ y $b$ , y por lo tanto, su máximo común divisor. Ninguno de los pasos modifica el conjunto de 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 igual al 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, por lo tanto, el producto 6 de $2 d = 2 1$ y $a = b = 3$ .

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

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

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

La complejidad computacional se suele expresar en términos de la longitud $n$ de la entrada. En este caso, esta longitud es $n = log a + log b$ , y la complejidad es, por lo tanto,

O(n^{2})

.

Algoritmo del MCD de Lehmer

El algoritmo de Lehmer se basa en la observación de que los cocientes iniciales producidos por el algoritmo de Euclides pueden determinarse a partir de los primeros dígitos; esto resulta útil para números mayores que una palabra de computadora . En esencia, se extraen los dígitos iniciales, que suelen formar una o dos palabras de computadora, y se aplica el algoritmo de Euclides a estos números más pequeños, siempre que se garantice que los cocientes sean los mismos que se obtendrían con los números originales. Los cocientes se recopilan en una pequeña matriz de transformación de 2x2 (una matriz de 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 (véase más adelante) 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 por hardware para la mayoría de las operaciones. De hecho, la mayoría de los cocientes son muy pequeños, por lo que un número considerable de pasos del algoritmo euclidiano se pueden agrupar en una matriz de 2x2 de 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

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

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

,

pero lo más común es que el MCM se calcule a partir del MCD.

Utilizando la función $f$ de Thomae ,

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

lo cual se generaliza a números racionales $a$ y $b$ o números reales conmensurables .

Keith Slavin ha demostrado que para impar $a \geq 1$ :

\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 b complejo . ^{[ 16 ]} Wolfgang Schramm ha demostrado que

\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 . ^{[ 17 ]}

Complejidad

La complejidad computacional del cálculo del máximo común divisor ha sido ampliamente estudiada. ^{[ 18 ]} Si se utiliza el algoritmo euclidiano y los algoritmos elementales para la multiplicación y la división, el cálculo del máximo común divisor de dos enteros de como máximo $n$ bits es $O (n 2)$ . Esto significa que el cálculo del máximo común divisor tiene, salvo 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 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 de $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 descritas anteriormente son válidas para los modelos de computación habituales , específicamente las máquinas de Turing de cintas múltiples y las máquinas de acceso aleatorio .

El cálculo del máximo común divisor pertenece, por lo 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 del MCD esté en NC , por lo que no hay una forma conocida de paralelizarlo eficientemente; tampoco se sabe que sea P-completo , lo que implicaría que es improbable que sea posible paralelizar eficientemente el cálculo del MCD. Shallcross et al. demostraron que un problema relacionado (EUGCD, determinar 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 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 $n 1+ ε$ procesadores. ^{[ 20 ]} Los algoritmos aleatorios pueden resolver el problema en tiempo $O ((log n) 2)$ en $O\left(e^{\sqrt {n\log n}}\right)$ procesadores (esto es superpolinomial ). ^{[ 21 ]}

Propiedades

Para cada entero positivo $a$ , $mcd(a, a) = a$ .
Todo divisor común de $a$ y $b$ es un divisor de $mcd(a, b)$ .
$mcd(a, b)$ , donde a y b no son ambos cero, puede definirse alternativamente y de forma equivalente como el entero positivo más pequeño d que puede escribirse en la forma $d = a \cdot p + b \cdot q$ , donde p y q son enteros. Esta expresión se denomina identidad de Bézout . Los números p y q de esta forma pueden calcularse con el algoritmo euclidiano extendido .
$mcd(a, 0) = | a |$ , para $a \neq 0$ , ya que cualquier número es divisor de 0, y el mayor divisor de a es $| a |$ . ^{[ 2 ]}^{[ 5 ]} Este se suele utilizar 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 \cdot a, m \cdot b) = m \cdot mcd(a, b)$ .
Si m es cualquier entero, entonces $mcd(a + m \cdot b, b) = mcd(a, b)$ . Equivalentemente, $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$ .
Si $mcd(a, b) = d$ , entonces $mcd(a / d, b / d) = 1$ .
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 usar para denotar el MCD de múltiples argumentos.
El MCD es una función multiplicativa en el siguiente sentido: si a ₁ y a ₂ son primos relativos, entonces $mcd(a 1 \cdot a 2, b) = mcd(a 1, b)\cdotmcd(a 2, b)$ .
$mcd(a, b)$ está estrechamente relacionado con el mínimo común múltiplo $mcm(a, b)$ : tenemos
$mcd(a, b)\cdotlcm(a, b) = | un \cdot segundo |$ .

Esta fórmula se usa a menudo para calcular el mínimo común múltiplo: 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 la propiedad distributiva 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 1 e 1 p 2 e 2 \cdot\cdot\cdot p m e m$ y $b = p 1 f 1 p 2 f 2 \cdot\cdot\cdot p m f m$ donde $e i \geq 0$ y $f i \geq 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) \cdot\cdot\cdot p m min(e m, f m)$ .
A veces resulta útil definir $mcd(0, 0) = 0$ y $mcm(0, 0) = 0$ porque entonces los números naturales se convierten en un retículo distributivo completo con MCD como intersección y mcm como unión. ^[²²^] Esta extensión de la definición también es compatible con la generalización para anillos conmutativos que se presenta a continuación.
En un sistema de coordenadas cartesianas , $mcd(a, b)$ puede interpretarse como el número de segmentos entre puntos con coordenadas enteras 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, demostrable considerando el algoritmo euclidiano en base n : ^[²³^]
$mcd(n a - 1, n b - 1) = n mcd(a, b) - 1$ .
Una identidad que involucra la función totiente de Euler :
$\gcd(a,b)=\sum _{k|a{\text{ y }}k|b}\varphi (k).$
Función sumativa del MCD (función aritmética de Pillai):

$\sum _{k=1}^{n}\gcd(k,n)=\sum _{d|n}d\varphi \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)$ dónde $\nu _{p}(n)$ es la valoración $p$ -ádica. (secuencia A018804 en la OEIS )

Probabilidades y valor esperado

En 1972, James E. Nymann demostró que $k$ 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 ]} (Véase coprimo para una derivación). Este resultado se extendió en 1987 para demostrar que la probabilidad de que $k$ enteros aleatorios tengan un máximo común divisor $d$ es $d - k /ζ(k)$ . ^{[ 25 ]}

Utilizando esta información, se puede observar (de manera informal) 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 / ζ (2)$ , por lo que tenemos

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

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

\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 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. ^{[ 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 $a 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 de integridad , entonces dos MCD cualesquiera de $a$ y $b$ deben ser elementos asociados , ya que por definición uno debe dividir al otro. De hecho, si existe un MCD, cualquiera de sus asociados también lo es.

La existencia de un máximo común divisor (MCD) no está garantizada en dominios de integridad arbitrarios. Sin embargo, si $R$ es un dominio de factorización única o cualquier otro dominio de MCD , entonces cualquier par de elementos tiene un MCD. Si $R$ es un dominio euclidiano en el que la división euclidiana se define algorítmicamente (como ocurre, por ejemplo, cuando $R = F [X],$ donde $F$ es un cuerpo , o cuando $R$ es el anillo de 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 un máximo común divisor (MCD):

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+{\sqrt {-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 ocurre con $1+{\sqrt {-3}}$ , pero no están asociados, por lo que no hay un máximo común divisor de $a$ y $b$ .

De acuerdo con la propiedad de Bézout, en cualquier anillo conmutativo podemos considerar la colección de elementos de la forma $pa + qb$ , donde $p$ y $q$ recorren el 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 de ideales principales o DIP), este ideal será idéntico al conjunto de múltiplos de algún elemento $d$ del anillo ; entonces, este $d$ es el máximo común divisor de $a$ y $b$ . Pero el ideal $(a, b)$ puede ser útil incluso cuando no existe un máximo común divisor de $a$ y $b$ . (De hecho, Ernst Kummer utilizó este ideal como sustituto del MCD en su tratamiento del Último Teorema de Fermat , aunque lo concibió como el conjunto de múltiplos de algún elemento $d hipotético o$ ideal del anillo , de donde proviene el término en teoría de anillos).

Véase también

Notas

1 2 Long (1972 , pág. 33)
1 2 3 Pettofrezzo y Byrkit (1970 , pág. 34)
↑ Kelley, W. Michael (2004). The Complete Idiot's Guide to Algebra . Penguin. pág. 142. ISBN 978-1-59257-161-1..
↑ Jones, Allyn (1999). Números enteros, decimales, porcentajes y fracciones. Año 7. Pascal Press. pág. 16. ISBN 978-1-86441-378-6..
1 2 3 Hardy y Wright (1979 , pág. 20)
↑ 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 usan, ya que denominador se refiere afracciones, y dos fracciones no tienen un máximo común denominador (si dos fracciones tienen el mismo denominador, se obtiene un denominador común mayor multiplicando todos los numeradores y denominadores por el mismonúmero entero).
↑ Barlow, Peter ; Peacock, George ; Lardner, Dionysius ; 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. .
↑ Algunos autores usan $(a, b)$ ,^{[ 1 ]}^{[ 2 ]}^{[ 5 ]} pero esta notación suele ser ambigua. Andrews (1994 , p. 16) lo explica así: "Muchos autores escriben $(a, b)$ para $mcd(a, b)$ . Nosotros no lo hacemos, porque a menudo usaremos $(a, b)$ para representar un punto en el plano euclidiano."
↑ Thomas H. Cormen, et al. , Introducción a los algoritmos (2.ª edición, 2001) ISBN 0262032937pág. 852
↑ Bernard L. Johnston, Fred Richman, Números y simetría: Una introducción al álgebra ISBN 084930301Xpág. 38
↑ Martyn R. Dixon, et al. , Introducción a las estructuras algebraicas esenciales ISBN 1118497759pág. 59
↑ p. ej., cálculo de Wolfram Alpha y Máximos
↑ Jonathan Katz, Yehuda Lindell, Introducción a la criptografía moderna ISBN 1351133012, 2020, sección 9.1.1, pág. 45
↑ Weisstein, Eric W. "Máximo común divisor" . mathworld.wolfram.com . Consultado el 30 de agosto de 2020 .
↑ "Máximo común divisor" . www.mathsisfun.com . Consultado el 30 de agosto de 2020 .
↑ Slavin, Keith R. (2008). "Q-Binomiales y el máximo común divisor" . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8. University of West Georgia , Charles University in Prague : A5 . Recuperado el 26 de mayo de 2008 .
↑ 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 West Georgia , Universidad Carolina de Praga : A50 . Recuperado el 25 de noviembre de 2008 .
↑ 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.
↑ 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) del original el 5 de septiembre de 2006.
↑ Chor, B. ; Goldreich, O. (1990). "Un algoritmo paralelo mejorado para el MCD entero". Algorithmica . 5 ( 1– 4): 1– 10. doi : 10.1007/BF01840374 . S2CID 17699330 .
↑ Adleman, LM; Kompella, K. (1988). «Using smoothness to achieve parallelism». 20th Annual ACM Symposium on Theory of Computing . Nueva York. pp. 528–538 . doi : 10.1145/62212.62264 . ISBN 0-89791-264-0. S2CID 9118047 .
↑ 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 a 40. ISBN 978-3-0348-0405-9.Nota al pie 27, pág. 9: «Por ejemplo, los números naturales con mcd (máximo común divisor) como operación de intersección y mcm (mínimo común múltiplo) como operación de unión determinan un retículo (distributivo completo)». Incluir estas definiciones para el 0 es necesario para este resultado: si se omite el 0 del conjunto de números naturales, el retículo resultante no es completo.
↑ Knuth, Donald E .; Graham, RL ; Patashnik, O. (marzo de 1994). Matemáticas concretas: Fundamentos para la informática . Addison-Wesley . ISBN 0-201-55802-5.
↑ Nymann, JE (1972). "Sobre la probabilidad de que $k$ enteros positivos sean primos relativos" . Journal of Number Theory . 4 (5): 469– 473. Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .
↑ 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 .
↑ 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 los números . Dover. ISBN 978-0-486-68252-5.
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 (2.ª 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 .

Lecturas adicionales

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 . Un panorama del álgebra moderna , cuarta edición. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "El algoritmo euclidiano."

Enlaces externos

Gráfica de la función mcd(x,y) = y: https://www.desmos.com/calculator/6nizzenog5

[Long_1972_33-1] 1 2 Long (1972 , pág. 33)

[Pettofrezzo_1970_34-2] 1 2 3 Pettofrezzo y Byrkit (1970 , pág. 34)

[3] Kelley, W. Michael (2004). The Complete Idiot's Guide to Algebra . 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..

[Hardy&Wright_1979_20-5] 1 2 3 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 usan, ya que denominador se refiere afracciones, y dos fracciones no tienen un máximo común denominador (si dos fracciones tienen el mismo denominador, se obtiene un denominador común mayor multiplicando todos los numeradores y denominadores por el mismonúmero entero).

[7] Barlow, Peter ; Peacock, George ; Lardner, Dionysius ; 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 usan $(a, b)$ ,^{[ 1 ]}^{[ 2 ]}^{[ 5 ]} pero esta notación suele ser ambigua. Andrews (1994 , p. 16) lo explica así: "Muchos autores escriben $(a, b)$ para $mcd(a, b)$ . Nosotros no lo hacemos, porque a menudo usaremos $(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 0262032937pág. 852

[10] Bernard L. Johnston, Fred Richman, Números y simetría: Una introducción al álgebra ISBN 084930301Xpág. 38

[11] Martyn R. Dixon, et al. , Introducción a las estructuras algebraicas esenciales ISBN 1118497759pág. 59

[12] . ej., cálculo de Wolfram Alpha y Máximos

[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. University of West Georgia , Charles University in Prague : A5 . Recuperado 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 West Georgia , Universidad Carolina de Praga : A50 . Recuperado 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) del original el 5 de septiembre de 2006.

[20] Chor, B. ; Goldreich, O. (1990). "Un algoritmo paralelo mejorado para el MCD entero". Algorithmica . 5 ( 1– 4): 1– 10. doi : 10.1007/BF01840374 . S2CID 17699330 .

[21] Adleman, LM; Kompella, K. (1988). «Using smoothness to achieve parallelism». 20th Annual ACM Symposium on Theory of Computing . 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 a 40. ISBN 978-3-0348-0405-9.Nota al pie 27, pág. 9: «Por ejemplo, los números naturales con mcd (máximo común divisor) como operación de intersección y mcm (mínimo común múltiplo) como operación de unión determinan un retículo (distributivo completo)». Incluir estas definiciones para el 0 es necesario para este resultado: si se omite el 0 del conjunto de números naturales, el retículo resultante no es completo.

[23] Knuth, Donald E .; Graham, RL ; Patashnik, O. (marzo de 1994). Matemáticas concretas: Fundamentos para la informática . Addison-Wesley . ISBN 0-201-55802-5.

[nymann-24] Nymann, JE (1972). "Sobre la probabilidad de que $k$ enteros positivos sean primos relativos" . Journal of Number Theory . 4 (5): 469– 473. Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .

[chid-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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[

[

[ 24 ]

[ 25 ]

[ 26 ]