De las matemáticas, el divisor común más grande (gcd) del, conocido a veces como el factor común más grande (gcf) del o factor común más alto (hcf) del, de dos números enteros diferentes a cero es el número entero positivo más grande que el divide ambos números sin el resto .

Descripción

El divisor común más grande del un y del b se escribe como gcd ( un,   b ), o a veces simplemente como ( un,   b ). Por ejemplo,   del gcd (12, 18); =  6, gcd (− 4,   )   14; =  2 y   del gcd (5, 0); =  5. Dos números se llaman el coprimero del o el relativamente primero si su divisor común más grande iguala 1. por ejemplo, 9 y 28 son relativamente primeros.

El divisor común más grande es útil para reducir las fracciones vulgares para ser en los términos más bajos . Por ejemplo, gcd (42, 56) =14, por lo tanto, $del$

l {42 \ sobre 56} = {3 \ cdot 14 \ sobre 4 \ cdot 14} = {3 \ sobre 4}.

¡Calculando el gcd aritmético -->

Los divisores comunes más grandes pueden en principio ser computados determinando las facturizaciones de la prima de los dos números y comparando factores, como en el ejemplo siguiente: para computar el gcd (18.84), encontramos las facturizaciones primeras 18  =  2·3² y 84  =  2²·3·7 y notan que el " overlap" de las dos expresiones está 2·3; tan   del gcd (18. En la práctica, este método es solamente factible para los números muy pequeños; la computación de facturizaciones primeras en general dura lejos demasiado.

Un método mucho más eficiente es el algoritmo euclidiano, que utiliza el algoritmo de división conjuntamente con la observación que el gcd de dos números también divide su diferencia: divisoria 84 por 18 para conseguir un cociente de 4 y un resto de 12. Entonces divisoria 18 por 12 para conseguir un cociente de 1 y un resto de 6. Entonces la divisoria 12 por 6 para conseguir un resto de 0, así que significa que 6 sea el gcd.

Las series de cocientes generados por el algoritmo euclidiano componen una fracción continua .

Si el un y el b no son ambo cero, el divisor común más grande del un y del b puede ser computado usando el menos múltiplo común (lcm) del un y del b : $del$

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

Características

Cada divisor común del un y del b es un divisor del gcd ( un,   b ).
gcd del

( un,   el b ), donde no están ambo cero el un y el b, se puede definir alternativo y equivalente como el positivo más pequeño d del número entero que se puede escribir en el   del d de la forma; =  un ·   del p ; +  b · q donde están números enteros el p y el q . Esta expresión se llama la identidad de Bézout. El p de los números y el q como esto se pueden computar con el algoritmo euclidiano ampliado .
gcd del

( un,   0) = | un |, para el un ≠ 0 de, puesto que cualquier número es un divisor de 0, y el divisor más grande del un está | un |. Esto se utiliza generalmente como el caso bajo en el algoritmo euclidiano.

si el un divide el b del producto · c, y gcd ( un,     del b ); =  el d, entonces un /un d divide el c .

si el m es un número entero no negativo, entonces gcd ( m · un,   m ·   del b ); =  m ·gcd ( un,   b ).

si el m es cualquier número entero, entonces gcd ( un   de ; +  m · b,     del b ); =  gcd ( un,   b ). Si el m es un divisor común diferente a cero del al y del b, entonces gcd ( un /un m,     del b /del m ); =  gcd ( un,   )/ m del b .

el gcd es una función multiplicativa en el sentido siguiente: si el un ₁ y el un ₂ son relativamente primeros, entonces gcd ( un ₁· un ₂,   b ) = gcd ( un ₁,   b )·gcd ( un ₂,   b ).

el gcd es una función comutativa : gcd ( un, b ) = gcd ( b, un ).

el gcd es una función asociativa : gcd ( un, gcd ( b, c )) = gcd (gcd ( un, b ), c ).

el gcd de tres números se puede computar como gcd ( un,   b,   c ) = gcd (gcd ( un,   b ),   c ), o en una cierta manera diferente aplicando commutativity y associativity. Esto se puede ampliar a cualquier número de números.
gcd del

( un,   el b ) es estrechamente vinculado al menos lcm del múltiplo común ( un,   b ): tenemos del
gcd de ( un,   b )·lcm ( un,     del b ); =  un · b . el
de esta fórmula es de uso frecuente computar menos múltiplos comunes: un primer computa el gcd con el algoritmo de Euclid y después divide el producto de los números dados por su gcd. Las versiones siguientes Distributivity son verdad: gcd del ( un,   lcm ( b,   c ))  =  lcm (gcd ( un,   b ),   gcd ( un,   c )) lcm del
( un,   gcd ( b,   c ))  =  gcd (lcm ( un,   b ),   lcm ( un,   c )).

es útil definir el gcd (0,   0)   =  0 y lcm (0,   0)   =  0 porque entonces los números naturales se convierten en un enrejado distributivo completo con el gcd como reuniones y lcm como ensamblan operación. Esta extensión de la definición es también compatible con la generalización para los anillos comutativos dados abajo.

en un sistema coordinado, gcd ( de cartesiano un,   el b ) se puede interpretar como el número de puntos con coordenadas integrales en la línea recta que ensambla los puntos (0,   0) y ( un,   b ), excluyendo (0,   0).

Probabilidades y valor previsto

La probabilidad que dos números enteros (ilimitados) aleatoriamente elegidos $A$ y $B$ tienen un divisor común más grande dado $d$ es $6\; \backslash \; sobre\; \{\backslash \; pi^2d^2\}$. Esto sigue de la caracterización del $gcd\; (A,\; B)$ como el número entero $d$ tales que $d|A,\; B$ y $A/d$ y $B/d$ son coprimeros. La probabilidad de dos números enteros que comparten un factor $d$ es el $d^\; \{-\; 2\}$. La probabilidad eso dos números enteros son coprimeros son $1/\backslash \; la\; zeta\; (2)=6/\backslash \; pi^2$. (Véase el coprimero para una derivación.)

Usar esta información, el el valor previsto de la función del divisor común más grande puede ser computado. Esto es

$\backslash \; mathrm\; \{E\}\; (\backslash \; mathrm\; \{2\})\; =\; \backslash \; sum\_\; \{d=1\}\; ^\; \{\backslash \; infty\}\; d\; \backslash \; frac\; \{6\}\; \{\backslash \; pi^2d^2\}\; =\; \backslash \; frac\; \{6\}\; \{\backslash \; pi^2\}\; \backslash \; sum\_\; \{d=1\}\; ^\; \{\backslash \}\; infty\; \backslash \; frac\; \{1\}\; \{d\}$

Esta última adición es la serie armónica, que diverge. Por lo tanto el valor previsto del divisor común más grande de dos variables no está bien definido. Éste no es el caso generalmente sin embargo. Para el divisor común más grande de las variables del $k\; \backslash \; GE\; 3$, el valor previsto está bien definido, y por la discusión antedicha, está

$\backslash \; mathrm\; \{E\}\; (k)\; =\; \backslash \; sum\_\; \{d=1\}\; ^\; \{\backslash \; infty\}\; d^\; \{1-k\}\; \backslash \; zeta\; (=\; \backslash \; frac\; del\; k)^\; \{-\; 1\}\; \{\backslash \; zeta\; (k-1)\}\{\backslash \; zeta\; (k)\}$.

donde $\backslash \; zeta\; (k)$ es la función de zeta de Riemann .

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

si todos los números enteros x se limitan como $m\; \backslash \; GE\; x\; \backslash \; GE\; 1$ entonces los resultados se pueden ampliar al $\backslash \; al\; mathrm\; \{E\}\; (k\; del,\; m)\; =\; \backslash \; frac\; \{\backslash \; d^\; del\; ^\; del\; sum\_\; \{d=1\}\; \{m\}\; \{1-k\}\}\; \{\backslash \; t^\; del\; ^\; del\; sum\_\; \{t=1\}\; \{m\}\; \{-\; k\}\}\; =\; \backslash \; frac\; \{\backslash \; zeta\; (k-1)\; -\; \backslash \; -\; \backslash \; zeta\; (k,\; m+1)\}$ de la zeta (k-1, m+1)} {\ zeta (k). donde $\backslash \; zeta\; (k,\; m)$ es la función de zeta de Hurwitz .

si diversos $m$ se saben para diverso $x$ entonces se toma el $m$ más bajo.

El gcd en anillos comutativos

El divisor común más grande se puede definir más generalmente para los elementos de un anillo comutativo arbitrario.

Si el R es un anillo comutativo, y el un y el b está en el R, después un d del elemento del R se llama un divisor común un y del b si divide el un y el b (es decir, si hay el x de los elementos y el y en el R tales que el d ·   del x ; =  un y d ·   del y ; =  b ). Si el d es un divisor común del al y el b, y cada divisor común del un y el b divide el d, después el d se llama un divisor común más grande un y del b .

Observar eso con esta definición, el de dos elementos un y el b pueden muy bien tener varios divisores comunes más grandes, o ningúno. Pero si el R es gcd del dominio un integral algunos dos entonces del un y un b deben ser los elementos del asociado. También, si el R es un dominio de facturización única, después cualquier dos elementos tener un gcd. Si el R es un dominio euclidiano entonces una forma del algoritmo euclidiano se puede utilizar para computar los divisores comunes más grandes.

Lo que sigue es un ejemplo de un dominio integral con dos elementos que no tengan un gcd:

$R\; =\; \backslash \; mathbb\; \{Z\}\; \backslash \; ido,\; \backslash \; patio\; a\; =\; 4\; =\; 2\; \backslash \; cdot\; 2\; =\; \backslash \; ido\; (1+\; \backslash \; raíz\; cuadrada\; \{-\; 3\}\; \backslash \; derecho)\; \backslash \; ido\; (1\; \backslash \; raíz\; cuadrada\; \{-\; 3\}\; \backslash \; derecho),\; \backslash \; patio\; b\; =\; \backslash \; ido\; (1+\; \backslash \; raíz\; cuadrada\; \{-\; 3\}\; \backslash )\; derecho\; \backslash \; cdot\; 2$ Los elementos $1+\; \backslash \; raíz\; cuadrada\; \{-\; 3\}$ y $2$ son el " dos; divisors" común máximo; (es decir cualquier divisor común que sea un múltiplo de 2 se asocia a 2, los mismos asimientos para $1+\; \backslash \; la\; raíz\; cuadrada\; \{-\; 3\}$), sino que él no es asociado, tan no hay divisor común más grande del al y del b .

Correspondencia a la característica de Bezout podemos, en cualquier anillo comutativo, considerar la colección de elementos del $p\; de\; la\; forma\; a\; +\; q\; b$, donde el p y el q se extienden sobre el anillo. Éste es el ideal generado por el un y el b, y es simplemente denotado el $(a,\; b)$. En un anillo todo cuyos de ideales ser principal (un dominio de ideal principal o PID), este ideal ser idéntico con el sistema de múltiplos de un cierto d del elemento del anillo; entonces este d es un divisor común más grande del al y del b . Pero el $ideal\; (a,\; b)$ puede ser útil incluso cuando no hay divisor común más grande del al y del b . (De hecho, el Ernst Kummer utilizó este ideal como reemplazo para un gcd en su tratamiento del teorema pasado de Fermat, aunque él lo previera como el sistema de múltiplos de algún hipotético, o del ideal, d del elemento del anillo, de dónde el término anillo-teórico.)

Ver también

menos múltiplo común
El denominador común más bajo
Algoritmo binario GCD
Algoritmo euclidiano
Algoritmo euclidiano extendido
El divisor común más grande de dos polinomios

.

Zenithic

Giuseppa Eleonora Barbapiccola

Random links:

Nuez dura, Mississippi | Capa monomolecular | Lista de líderes estatales en 1684 | Enero de Quay | Gentoox