Máximo común divisor

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

entero positivo más grande que divide dos o más enteros

En matemáticas, la mayor divisor común ()GCD) de dos o más enteros, que no son todos cero, es el entero positivo más grande que divide cada uno de los enteros. Para dos enteros x, Sí., el mayor divisor común x y Sí. es denotado ${displaystyle gcd(x,y)}$ . Por ejemplo, el GCD de 8 y 12 es 4, es decir, ${displaystyle gcd(8,12)=4}$ .

En el nombre "máximo común divisor", el adjetivo "mayor" puede ser reemplazado por "más alto", y la palabra "divisor" puede ser reemplazado por "factor", por lo que otros nombres incluyen máximo común divisor (hcf), etc. Históricamente, otros nombres para el mismo concepto han incluida la máxima medida común.

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

Resumen

Definición

El máximo común divisor (MCD) de dos enteros distintos de cero $a$ y $b$ es el mayor entero positivo $d$ tal que $d$ es un divisor de ambos $a$ y $b$ ; es decir, hay números enteros $e$ y $f$ tal que $a = de$ y $b = df$ , y $d$ es el entero más grande. El GCD de $a$ y $b$ generalmente se denota como $gcd(a, b)$ .

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

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

El GCD 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 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 producto de dos números enteros de varias maneras diferentes:

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

Así la lista completa de divisores de 54 años ${displaystyle 1,2,3,6,9,18,27,54}$ . Del mismo modo, los divisores de 24 son ${displaystyle 1,2,3,4,6,8,12,24}$ . Los números que estas dos listas tienen en común son 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 los dos números de esta manera generalmente no es eficiente, especialmente para números grandes que tienen muchos divisores. Métodos mucho más eficientes se describen en § Cálculo.

Números coprimos

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

Una vista geométrica

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."

Un rectángulo de 24 por 60 está cubierto con diez azulejos cuadrados de 12 por 12, donde 12 es el GCD de 24 y 60. Más generalmente, un a-por-b rectángulo se puede cubrir con azulejos cuadrados de longitud lateral c sólo si c es un divisor común 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 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

Reducción de fracciones

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

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

Mínimo común múltiplo

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

operatorname{lcm}(a,b)=frac{|acdot 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 GCD 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^máx(4,2) · 3^máx(1,2) · 5^máx(0,1) = 2⁴ · 3² · 5¹ = 720.

En la práctica, este método solo es factible para números pequeños, ya que calcular factorizaciones en números primos 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$ tal 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 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 $gcd(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 gcf(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 variante que sigue.

Algoritmo euclidiano

Animación mostrando una aplicación del algoritmo de Euclidean para encontrar el mayor divisor común 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)$ por $(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 gcd(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 $gcd(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 Euclides se pueden determinar basándose solo 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, normalmente formando 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 son los mismos que se obtendrían con el original. números. Los cocientes se recopilan en una pequeña matriz de transformación de 2 por 2 (una matriz de enteros de una sola palabra) para reducir los números originales. Este proceso se repite hasta que los números son lo suficientemente pequeños para que el algoritmo binario (ver más abajo) sea más eficiente.

Este algoritmo mejora la velocidad porque reduce la cantidad 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 se puede recopilar una buena cantidad de pasos del algoritmo euclidiano en una matriz de 2 por 2 de 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 GCD binario

El algoritmo GCD binario usa solo la resta y la división por 2. El método es el siguiente: Sean a y b los dos enteros no negativos. Sea el entero d 0. Hay cinco posibilidades:

a = b.

Como mcd(a, a) = a, el MCD deseado es a × 2^d (ya que a y b se cambian en los otros casos, y d registra el número de veces que a y b se han dividido por 2 en el siguiente paso, el MCD del par inicial es el producto de a y 2^d).

Ambos a y b son incluso.

Entonces 2 es un divisor común. Divide tanto a como b entre 2, incrementa d en 1 para registrar el número de veces que 2 es un divisor común y continúa.

a es incluso b Es extraño.

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

a es extraño b es incluso.

Entonces 2 no es un divisor común. Divide b entre 2 y continúa.

Ambos a y b son extraños.

Como mcd(a,b) = mcd(b,a), si un < b luego intercambia a y b. El número c = a − b es positivo y menor que a. Cualquier número que divide a a y b también debe dividir a c por lo que cada divisor común de a y b es también un divisor común de b y c. Del mismo modo, a = b + c y todo divisor común de b y c es también un divisor común de a y b. Entonces los dos pares (a, b) y (b, c) tienen los mismos divisores comunes, y así mcd(a,b) = mcd(b,c). Además, como a y b son ambos 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 GCD.

Cada uno de los pasos anteriores reduce al menos uno de a y b y los deja no negativos, por lo que solo se pueden repetir un número finito de veces. Así, finalmente, el proceso da como resultado a = b, el caso final. 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 GCD binario es particularmente fácil de implementar en computadoras binarias. Su complejidad computacional es

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 ${displaystyle n=log a+log b,}$ y la complejidad es así

O(n^{2})

Otros métodos

gcd(1,x) = y,

o la función de Thomae. Sombrero 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, se puede calcular el máximo común divisor de a y b usando el mínimo común múltiplo (MCM) de a y b:

{displaystyle gcd(a,b)={frac {|acdot 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,

gcd(a,b)=afleft({frac {b}{a}}right),

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

Keith Slavin ha demostrado que para impar a ≥ 1:

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

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

gcd(a,b)=sum limits _{k=1}^{a}exp(2pi ikb/a)cdot sum limits _{dleft|aright.}{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 de la computación de los más grandes divisores comunes ha sido ampliamente estudiada. Si uno utiliza el algoritmo de Euclidean y los algoritmos elementales para la multiplicación y división, la computación del divisor más grande común de dos enteros de al menos $n$ bits es ${displaystyle O(n^{2}).}$ Esto significa que la computación de mayor divisor común tiene, hasta un factor constante, la misma complejidad que la multiplicación.

Sin embargo, si se utiliza un algoritmo de multiplicación rápida, se puede modificar el algoritmo de Euclidean para mejorar la complejidad, pero la computación de un divisor común más grande se vuelve más lenta 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 mayor divisor común tiene una complejidad ${displaystyle Oleft(T(n)log nright).}$ Esto implica que el algoritmo más rápido conocido tiene una complejidad ${displaystyle Oleft(n,(log n)^{2}right).}$

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 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 existe una 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 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 equivalente en NC 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 está. Dado que NC contiene NL, también se desconoce si existe un algoritmo de espacio eficiente para calcular el GCD, incluso para máquinas de Turing no deterministas.

Aunque el problema no se sabe que está NC, algoritmos paralelos asintomáticamente más rápido que el algoritmo de Euclidean existen; el algoritmo determinista más rápido conocido es por Chor y Goldreich, que (en el modelo CRCW-PRAM) puede resolver el problema en $O () n /log n)$ tiempo con $n 1+ε$ procesadores. algoritmos aleatorios pueden resolver el problema en $O (log n) 2)$ tiempo ${displaystyle exp left(Oleft({sqrt {nlog n}}right)right)}$ procesadores (esto es superpolítico).

Propiedades

Cada divisor común a y b es un divisor de gcd(a, b).
gcd(a, b), donde a y b no son ambos cero, se puede definir alternativa y equivalentemente como el número más pequeño positivo d que se puede escribir en la forma d = a⋅p + b⋅q, donde p y q son enteros. Esta expresión se llama identidad de Bézout. Números p y q como este puede ser calculado con el algoritmo de Euclidean extendido.
gcd(a, 0) = SilencioaSilencio, para a ل 0, ya que cualquier número es un divisor de 0, y el mayor divisor de a es la vidaaSilencio. Esto se utiliza generalmente como el caso base en el algoritmo de Euclidean.
Si a divide el producto b⋅c, y gcd(a, b) d, entonces a/d divideciones c.
Si m es un entero positivo, entonces gcd(m⋅a, m⋅b) m⋅gcd(a, b).
Si m es cualquier entero, entonces gcd(a + m⋅b, b.a, b). Equivalentemente, gcd(a mod b,b.a,b).
Si m es un divisor común positivo a y b, entonces gcd(a/m, b/m.a, b)/m.
El GCD es una función conmutativa: gcd(a, b.b, a).
El GCD es una función asociativa: gcd(a, gcd(b, c) = gcd(gcd(a, b), c). Así gcd(a, b, c,...) se puede utilizar para denotar el GCD de múltiples argumentos.
El GCD es una función multiplicativa en el siguiente sentido: si a₁ y a₂ son relativamente primos, entonces gcd(a₁⋅a₂, b.a₁, b)⋅gcd(a₂, b).
gcd(a, b) está estrechamente relacionado con los múltiples menos comunes lcm(a, b): tenemos
gcd(a, b)⋅lcm(a, b.a⋅bSilencio.

Esta fórmula se utiliza a menudo para computar los múltiplos menos comunes: primero computa el GCD con el algoritmo de Euclid y luego divide el producto de los números dados por su GCD.

Las siguientes versiones de distribución son verdaderas:
gcd(a, lcm(b, c) = lcm(gcd(a, b), gcd(a, c)
lcm(a, gcd(b, c) = gcd(lcm(a, b), lcm(a, c).
Si tenemos las características principales ú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 a 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 completa celosía distributiva con GCD como reunión y LCM como operación de unión. Esta extensión de la definición también es compatible con la generalización de anillos conmutativos indicados a continuación.
En un sistema de coordenadas cartesianas, gcd(a, b) se puede interpretar como el número de segmentos entre puntos con coordenadas integrales en el segmento de línea recta que unen los puntos (0, 0) y ()a, b).
Para los enteros no negativos a y b, donde a y b no son ambos cero, provables considerando el algoritmo Euclideano en la basen:
gcd(n^a, 1, n^b −1) = n^gcd(a,b) − 1.
Una identidad que implica la función totiente de Euler:
${displaystyle gcd(a,b)=sum _{k|a{text{ and }}k|b}varphi (k).}$
${displaystyle sum _{k=1}^{n}gcd(k,n)=nprod _{p|n}left(1+nu _{p}(n)left(1-{frac {1}{p}}right)right)}$ Donde $nu _{p}(n)$ es la valoración p-adic.

Probabilidades y valor esperado

En 1972, James E. Nymann demostró que los números enteros k, elegidos de forma independiente y uniforme de {1,..., n}, son coprimos con probabilidad 1/ ζ(k) cuando n tiende al infinito, donde ζ se refiere a la función zeta de Riemann. (Ver coprimos 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).

Usando 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 GCD sea igual a d es d⁻²/ζ(2), y como ζ(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 ≥ 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.

Si $R$ es un anillo conmutativo, y $a$ y $b$ están en $R$ , luego un elemento $d$ de $R$ se denomina divisor común de $a$ y $b$ si divide a ambos $a$ y $b$ (es decir, si hay elementos $x$ y $y$ en $R$ tal que d ·x = a y d·y = b). Si $d$ es un divisor común de $a$ y $b$ , y todos los divisores comunes de $a$ y $b$ divide $d$ , entonces $d$ se denomina máximo común divisor de $a$ y b.

Con esta definición, dos elementos $a$ y $b$ puede muy bien tener varios máximos comunes divisores, o ninguno. Si $R$ es un dominio integral, entonces dos GCD de $a$ y $b$ deben ser elementos asociados, ya que por definición cualquiera de los dos debe 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 dos elementos cualquiera tienen un GCD y, en 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 enteros gaussianos), entonces los máximos comunes divisores se pueden calcular 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 un GCD:

R=mathbb {Z} left[{sqrt {-3}},,right],quad a=4=2cdot 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 un múltiplo de 2 está asociado a 2, lo mismo se aplica a 1 + √−3, pero no están asociados, por lo que no hay un máximo común divisor de $a$ y b.

Correspondiente a la propiedad Bézout podemos, en cualquier anillo conmutativo, considerar la colección de elementos de la forma pa + qb, donde $p$ y $q$ se extienden sobre 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 ideal principal o PID), este ideal será idéntico al conjunto de múltiplos de algún elemento del anillo d; entonces esta $d$ es el 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 usó este ideal como reemplazo de un GCD en su tratamiento del último teorema de Fermat, aunque lo visualizó como el conjunto de múltiplos de algún anillo hipotético, o ideal. elemento $d$ , de ahí el término de teoría de anillos).

Contenido relacionado

Más resultados...