Máximo común divisor

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

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

Esta noción se puede extender a polinomios (ver Máximo común divisor polinómico ) y otros anillos conmutativos (ver § En anillos conmutativos a continuación).

Descripción general

Definición

El máximo común divisor (MCD) de los números enteros $a$ y $b$ , al menos uno de los cuales es distinto de cero, es el mayor entero positivo $d$ tal que $d$ es 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 número entero más grande. El MCD de $a$ y $b$ generalmente se denota $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) = | un |$ . Este caso es importante como paso final del algoritmo euclidiano.

La definición anterior no es adecuada para definir $gcd(0, 0)$ , ya que no existe un entero mayor $n$ tal que $0 \times n = 0$ . Sin embargo, cero es su propio máximo divisor si mayor se entiende 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 , es decir, que $mcd(a, b)$ genera el mismo ideal que ${a, b}$ . ^[9]^[10]^[11] Esta convención es seguida por muchos sistemas de álgebra informática . ^[12] Sin embargo, algunos autores dejan $gcd(0, 0)$ sin definir. ^[13]

El MCD de $a$ y $b$ es su máximo común divisor positivo en la relación de divisibilidad de preorden . 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 euclidiano . 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 producto de dos números enteros de varias formas 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 ellos, el mayor es 6, por lo que es el máximo común divisor :

\gcd(54,24)=6.

Calcular todos los divisores de 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 coprimos

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

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 está cubierto con diez mosaicos cuadrados de 12 por 12, donde 12 es el MCD de 24 y 60. De manera más general, un *rectángulo* a por b se puede cubrir con mosaicos cuadrados de longitud de lado c únicamente . si c es 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 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 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

Reducir 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,

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

Minimo común multiplo

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

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

Cálculo

Usando factorizaciones primas

Los máximos divisores comunes se pueden calcular determinando las factorizaciones primas de los dos números y comparando 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 ^máx(1,2) · 5 ^máx(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 las factorizaciones primas lleva demasiado tiempo.

algoritmo de euclides

El método introducido por Euclides para calcular los máximos comunes divisores 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.$ .

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:

{\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{alineado}}

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

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

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

Al denotar este resto como $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 mcd(48,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 GCD binario

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

El algoritmo binario GCD se diferencia del algoritmo de Euclides esencialmente en dividir por dos cada número par que se encuentre durante el cálculo. Su eficiencia resulta del hecho de que, en la representación binaria, probar la paridad consiste en probar el dígito más a la derecha, y dividir 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 enteros positivos cuyo MCD se busca.

Si $a$ y $b$ son pares, divida ambos por dos hasta que al menos uno de ellos se vuelva impar; sea $d$ el número de estas divisiones emparejadas.
Si $a$ es par, divídelo entre dos hasta que quede impar.
Si $b$ es par, 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.
Mientras que a ≠ b hacer
- Si $a > b$ , entonces reemplace $a$ con $a - b$ y divida el resultado entre dos hasta que $a$ se vuelva impar (como $a$ y $b$ son ambos impares, hay, al menos, una división entre 2).
- Si $a < b$ , reemplace $b$ con $b - a$ y divida el resultado por dos hasta que $b$ se vuelva impar.
Ahora, $a = b$ , y el máximo común divisor es $2^{d}a.$

El paso 1 determina $d$ como 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 muestra que cuando el algoritmo se detiene, el resultado es correcto. El algoritmo finalmente se detiene, ya que cada paso divide al menos uno de los operandos por al menos $2$ . Además, el número de divisiones entre $2$ y, por 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, por tanto, el producto 6 de $2 d = 2 1$ y $a = b = 3$ .

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

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

El cuadrado en 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 generalmente viene dada en términos de la longitud $n$ de la entrada. Aquí, esta longitud es $n = log a + log b$ y, por lo tanto, la complejidad es

O(n^{2})

Algoritmo GCD 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 basándose únicamente en los primeros dígitos; esto es útil para números que son mayores que una palabra de computadora . En esencia, se extraen los dígitos iniciales, que normalmente forman una o dos palabras informáticas, 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 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 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 pueden 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 metodos

Si $a$ y $b$ son distintos de cero, el máximo común divisor de $a$ y $b$ se puede calcular usando 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 habitual es que el LCM se calcule a partir del MCD.

Usando la función $f$ de Thomae ,

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

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

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

\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 . ^[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 números enteros positivos a donde c _d ( k ) es la suma de Ramanujan . ^[17]

Complejidad

La complejidad computacional del cálculo de los máximos divisores comunes 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 2)$ . 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 del 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 conocido más rápido tiene una complejidad de $O (n (log n) 2)$ .

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 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 resolubles en tiempo polinomial. No se sabe que el problema GCD esté en NC , por lo que no se conoce ninguna 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 del MCD. Shallcross et al. demostró que un problema relacionado (EUGCD, determinación de la secuencia restante que surge durante el algoritmo euclidiano) es NC equivalente al problema de programación lineal entera con dos variables; si alguno de los problemas está en NC o es P-completo , el otro también lo estará. ^[19] Dado que NC contiene NL , también se desconoce si existe un algoritmo espacialmente eficiente 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 $O (n /logn) tiempo$ con $n 1+ ε$ procesadores. ^[20] Los algoritmos aleatorios pueden resolver el problema en $O ((log n) 2)$ tiempo en los procesadores ^[^{se necesita aclaración}^] (esto es superpolinomio ). ^[21] $\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 divisor de $mcd(a, b)$ .
$mcd(a, b)$ , donde a y b no son ambos cero, puede definirse alternativa y equivalentemente 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 números enteros. Esta expresión se llama identidad de Bézout . Números p y q como este se pueden calcular con el algoritmo euclidiano extendido .
$mcd(a, 0) = | un |$ , para $a \neq 0$ , ya que cualquier número es divisor de 0 y el máximo divisor de a es $| un |$ . ^[2]^[5] Esto 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 entero positivo, entonces $mcd(m \cdot a, m \cdot b) = m \cdotgcd(a, b)$ .
Si m es cualquier número entero, entonces $mcd(a + m \cdot 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 tanto, $gcd(a, b, c, ...)$ se puede utilizar 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)\cdotgcd(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 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 ciertas:
$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 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 encuentro 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 proporciona a continuación.
En un sistema de coordenadas cartesiano , $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 :
$\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$
$\sum _{k=1}^{n}\gcd(k,n)=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 está la valoración $p -ádica?$ $\nu _{p}(n)$

Probabilidades y valor esperado.

En 1972, James E. Nymann demostró que $k$ enteros, elegidos de forma independiente y uniforme entre ${1,..., n}$ , son coprimos con probabilidad $1/ ζ (k)$ cuando $n$ tiende al infinito, donde $ζ$ se refiere al zeta de Riemann. función . ^[24] (Ver coprimo 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)$ . ^[25]

Usando 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 / ζ (2)$ , y como $ζ (2) = π 2 /6$ tenemos

\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 sumatoria es la serie armónica , que diverge. Sin embargo, cuando $k \geq 3$ , el valor esperado está bien definido y, según 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.

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$ como $a b$ (es decir, si hay elementos $x$ e $y$ en $R$ tal que d · x = a y d · y = b ). Si $d$ es un divisor común de $a$ y $b$ , y cada 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, es muy posible que dos elementos $a$ y $b$ tengan varios máximos divisores comunes, o ninguno. Si $R$ es un dominio integral , 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 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 dos elementos cualesquiera tienen un MCD y, de manera más general, esto es cierto en los dominios de 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 campo , o cuando $R$ es el anillo de enteros gaussianos ), entonces los máximos divisores comunes pueden ser calculado utilizando 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 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 no hay máximo común divisor de $a$ y $b$ .

Correspondiente a 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 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 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 de anillo hipotético o ideal $d$ , de donde surge el término de teoría de anillos).

Ver también

Notas

^ ab Largo (1972, pág.33)
^ a b C Pettofrezzo y Byrkit (1970, p. 34)
^ Kelley, W. Michael (2004), La guía completa de álgebra para idiotas, Penguin, p. 142, ISBN 978-1-59257-161-1.
^ Jones, Allyn (1999), Números enteros, decimales, porcentajes y fracciones Año 7, Pascal Press, p. 16, ISBN 978-1-86441-378-6.
^ abc 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 ningún máximo común denominador (si dos fracciones tienen el mismo denominador, se obtiene un mayor denominador común multiplicando todos los numeradores y denominadores por el mismonúmero entero).
^ Barlow, Pedro ; Pavo real, George ; Lardner, Dionisio ; Aireado, Sir George Biddell ; Hamilton, HP ; Levy, A.; De Morgan, Augusto ; Mosley, Henry (1847), Enciclopedia de Matemáticas Puras, R. Griffin and Co., pág. 589.
^ Algunos autores utilizan $(a, b)$ , ^[1]^[2]^[5] pero esta notación suele ser ambigua. Andrews (1994, p. 16) explica esto como: "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 sistema euclidiano. avión."
^ Thomas H. Cormen, et al. , Introducción a los algoritmos (2.ª edición, 2001) ISBN 0262032937 , p. 852
^ Bernard L. Johnston, Fred Richman, Números y simetría: una introducción al álgebra ISBN 084930301X , p. 38
^ Martyn R. Dixon, et al. , Introducción a las estructuras algebraicas esenciales ISBN 1118497759 , p. 59
^ por ejemplo, cálculo de Wolfram Alpha y Maxima
^ Jonathan Katz, Yehuda Lindell, Introducción a la criptografía moderna ISBN 1351133012 , 2020, sección 9.1.1, p. 45
^ Weisstein, Eric W. "Mayor común divisor". mathworld.wolfram.com . Consultado el 30 de agosto de 2020 .
^ "Máximo factor común". www.mathsisfun.com . Consultado el 30 de agosto de 2020 .
^ Slavin, Keith R. (2008). "Q-binomios y máximo común divisor". ENTEROS: Revista electrónica de teoría combinatoria de números . Universidad de Georgia Occidental , Universidad Carolina de Praga . 8 : A5 . Consultado el 26 de mayo de 2008 .
^ Schramm, Wolfgang (2008). "La transformada de Fourier de funciones del máximo común divisor". ENTEROS: Revista electrónica de teoría combinatoria de números . Universidad de Georgia Occidental , Universidad Carolina de Praga . 8 : A50 . Consultado 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.). Profesional de Addison-Wesley. ISBN 0-201-89684-2.
^ Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "La equivalencia NC de la programación lineal entera plana y el MCD euclidiano" (PDF) . 34º Simposio IEEE. Fundamentos de la Informática . págs. 557–564. Archivado (PDF) desde el original el 5 de septiembre de 2006.
^ Chor, B .; Goldreich, O. (1990). "Un algoritmo paralelo mejorado para GCD entero". Algorítmica . 5 (1–4): 1–10. doi :10.1007/BF01840374. S2CID 17699330.
^ Adleman, LM; Kompella, K. (1988). "Usar la suavidad para lograr el paralelismo". 20º Simposio Anual ACM sobre Teoría de la Computación . Nueva York. págs. 528–538. doi :10.1145/62212.62264. ISBN 0-89791-264-0. S2CID 9118047.{{cite book}}: CS1 maint: location missing publisher (link)
^ Müller-Hoissen, Folkert; Walther, Hans-Otto (2012), "Dov Tamari (anteriormente Bernhard Teitler)", en Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim (eds.), Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift , Progress in Mathematics, vol. 299, Birkhäuser, págs. 1–40, ISBN 978-3-0348-0405-9. Nota a pie de página 27, pág. 9: "Por ejemplo, los números naturales con mcd (máximo común divisor) como encuentro y mcm (mínimo común múltiplo) como operación de unión determinan una red (distributiva completa)". Es necesario incluir estas definiciones para 0 para este resultado: si, en cambio, se omite 0 del conjunto de números naturales, la red resultante no está completa.
^ 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.
^ Nymann, JE (1972). "Sobre la probabilidad de que k enteros positivos sean primos relativos". Revista de teoría de números . 4 (5): 469–473. Código bibliográfico : 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 .

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

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