Máximo común divisor

En matemáticas, o máximo común divisor (MCD ou mdc)^[1] ou máximo divisor común^[2] de dous ou máis números enteiros é o maior número enteiro que os divide sen deixar resto.

Se a e b son números enteiros distintos de cero e se o número c é tal que c|a e á súa vez c|b, este número c denomínase divisor común dos números a e b.^[3] Cómpre observar que dous números enteiros calquera teñen divisores comúns; cando os únicos divisores comúns dos números a e b son 1 e -1, eses números chámanse primos entre si.

Un número enteiro d chámase máximo común divisor dos números a e b cando:

1. d é divisor común dos números a e b e
2. d é divisible por calquera outro divisor común dos números a e b.

Exemplo:

12 é o mcd de 36 e 60. Pois 12|36 e 12|60; á súa vez 12 é divisible por 1, -1, 2, -2, 3, -3, 4, -4, 6, -6, 12 e -12 que son divisores comúns de 36 e 60.^[4]

O tres métodos máis utilizados para o cálculo do máximo divisor común de dous números son:

O máximo común divisor de dous números pode calcularse determinando a descomposición en factores primos dos dous números e tomando os factores comúns elevados á menor potencia, o produto dos cales será o mcd.

Exemplo: para calcular o máximo común divisor de 48 e de 60 obtense da súa factorización en factores primos.

O mcd son os factores comúns co seu menor expoñente, isto é:

${\displaystyle \operatorname {mcd} (48;60)=2^{2}\cdot 3=12}$

Na práctica, este método só é operativo para números pequenos levando en xeral demasiado tempo calcular a descomposición en factores primos de dous números calquera.

Un método máis eficiente é o algoritmo de Euclides, que emprega o algoritmo da división xunto co feito de que o mcd de dous números tamén divide o resto obtido de dividir o maior entre o máis pequeno.

Exemplo 1: Se se divide 60 entre 48 dando un cociente de 1 e un resto de 12, o MCD será polo tanto divisor de 12. Despois divídese 48 entre 12 dando un resto de 0, o que significa que 12 é o mcd. Formalmente pode describirse como:

${\displaystyle \operatorname {mcd} (a,0)=a}$

${\displaystyle \operatorname {mcd} (a,b)=\operatorname {mcd} (b,a\,\mathrm {mod} \,b).}$

Exemplo 2: O MCD de 42 e 56 é 14. En efecto:

${\displaystyle \operatorname {mcd} (42,56)=14\,}$

operando:

${\displaystyle {\frac {42}{14}}=3\;,\quad {\frac {56}{14}}=4}$

O máximo divisor común tamén pode ser calculado empregando o mínimo común múltiplo. Se a e b son distintos de cero, entón o máximo divisor común de a e b obtense mediante a seguinte fórmula, que involucra o mínimo múltiplo común de a e b:

${\displaystyle \operatorname {mcd} (a,b)={\frac {a\cdot b}{\operatorname {MCM} (a,b)}}}$

O máximo común divisor de tres ou máis números pódese definir recursivamente empregando o método: ${\displaystyle \ \operatorname {mcd} (a,b,c)=\operatorname {mcd} (a,\operatorname {mcd} (b,c))}$.^[5][6]

1. Se ${\displaystyle \ \operatorname {mcd} (a,b)=d}$ entón ${\displaystyle \ \operatorname {mcd} \left({\frac {a}{d}},{\frac {b}{d}}\right)=1}$ 2. Se ${\displaystyle \ m}$ é un enteiro, ${\displaystyle \ \operatorname {mcd} (ma,mb)=|m|\cdot \operatorname {mcd} (a,b)}$ 3. Se ${\displaystyle \ p}$ é un número primo, entón ${\displaystyle \ \operatorname {mcd} (p,m)=p}$ o bien ${\displaystyle \ \operatorname {mcd} (m,p)=1}$ 4. Se ${\displaystyle d=\operatorname {mcd} (m,n),\ m=d'm'',\ n=d'n'',\ \operatorname {mcd} (m'',n'')=1}$, entón ${\displaystyle \ d=d'}$ 5. Se ${\displaystyle \ d'}$ é un divisor común de ${\displaystyle \ m}$ e ${\displaystyle \ n}$, entón ${\displaystyle d'\mid \operatorname {mcd} (m,n)}$ 6. Se ${\displaystyle \ m=nq+r}$, entón ${\displaystyle \operatorname {mcd} (m,n)=\operatorname {mcd} (n,r)}$ 7. Se ${\displaystyle \ m=p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}}\;\,\mathrm {y} \;\,n=p_{1}^{\beta _{1}}\cdots p_{k}^{\beta _{k}},\;\,\alpha _{i},\beta _{i}\geq 0,\;\,i=1,...,k}$, entón ${\displaystyle \operatorname {mcd} (m,n)=p_{1}^{\operatorname {min} (\alpha _{1},\beta _{1})}\cdots p_{k}^{\operatorname {min} (\alpha _{k},\beta _{k})}}$ Esta última propiedade indica que o máximo divisor común de dous números é o produto dos seus factores primos comúns elevados ao menor expoñente.

Xeometricamente, o máximo divisor común de a e b é o número de puntos de coordenadas enteiras que hai no segmento que une os puntos (0, 0) e (a, b), excluíndo o (0, 0).

1. Para calquera par de números enteiros a≠0, b≠0, existe un único mcd d ≥ 1.^[7]
2. O mcd. dos números a e b pode ser representado en forma de combinación linear destes números. Isto é (a, b) = ax + by
3. Se dous números enteiros son primos entre si, i.e. o seu mcd = 1 ou noutra notación (a, b) = 1, entón cómpre a representación ma + nb = 1 onde m e n son números enteiros (identidade de Bézout).
4. Se a|bc e (a, b) = 1, será a|c. Noutras palabras, se un número a divide un produto doutros dous números e é coprimo cun deles, entón divide necesariamente o outro número ou factor.^[8]
5. Cando un número a é coprimo cos números m e n, tamén o é co produto mn.
6. (a, b) é divisor de (a, bc)^[9]
7. t(a, b) = (ta, tb) para todo t enteiro^[10]
8. Se (m, b)= 1 entón (am, b)= (a, b)^[11]
9. Se (m, b)= 1, (am, n) = 1 entón (am, bn) = (a, b)
10. Para todo x, (a, b)= (b, a) = (a, -b) = (a, b + ax)^[12]
11. Por definición, (0, 0) = 0;^[13] deste xeito o mcd defínese en todo ℤ×ℤ.
12. (a, b) = b se e só se b|a, (ou sexa se a é múltiplo de b).
13. Se (a, b)= D, entón (an, bn) = Dn^[14]
14. mZ + nZ = (m, n)Z. Sumar senllos múltiplos de dous enteiros é o mesmo que considerar os múltiplos do seu máximo común divisor.^[15]
15. ${\displaystyle (a^{2},ab,b^{2})=(a,b)^{2}}$^[16]

• O mcd pódese estruturar como unha operación en ℤ; deste xeito a calquera par de enteiros, ou sexa a un elemento de ℤ×ℤ asígnalle un único elemento de ℤ.
• Para calquera par de enteiros (a, b) existe un enteiro non negativo d que é o seu máximo común divisor. Isto é a*b = (a, b) = d.
• O mcd goza da propiedade asociativa, como da propiedade conmutativa.
• O mcd posúe un elemento identidade, o cero, de modo tal que (a, 0)= (0, a)= a^[17]
• O mcd ten un comportamento dual que o mínimo común múltiplo, e aos enteiros non negativos a e b lígaos a ecuación ab = (a, b)[a, b]^[18]
• Propiedade do 1: (a, 1) = 1 para calquera enteiro a, pois o 1 é divisor de todos os enteiros, ou ben xera os elementos de ℤ.

O mcd emprégase para simplificar fraccións. Por exemplo, para simplificar a fracción ${\displaystyle \scriptstyle {\frac {48}{60}}}$ calcúlase primeiro o mcd(60, 48) = 12, dividíndose o numerador e o denominador da fracción inicial por 12 para obter a fracción simplificada ${\displaystyle \scriptstyle {\frac {4}{5}}}$.

O mcd tamén se emprega para calcular o mínimo común múltiplo de dous números. En efecto, o produto dos dous números é igual ao produto do seu máximo divisor común polo seu mínimo común múltiplo. Así, para calcular o mínimo común múltiplo de 48 e de 60, calcúlase primeiro o seu mcd, 12, sendo o seu mínimo común múltiplo ${\displaystyle \scriptstyle {\frac {48\cdot 60}{12}}=240}$.

O mcd e o algoritmo de Euclides empréganse na resolución de ecuacións diofánticas lineares con dúas incógnitas^[19] e para desenvolver un número racional en fraccións continuas.^[20]

• Andrews, George E. (1994) [1971]. Number Theory. Dover. ISBN 9780486682525. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862.
• Hardy, G. H.; Wright, E. M. (1979). An Introduction to the Theory of Numbers (Fifth ed.). Oxford: Oxford University Press. ISBN 978-0-19-853171-5. 
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp. 333–356.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950. 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766. 
• Saunders MacLane e Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "The Euclidean Algorithm."

• Weisstein, Eric W. «Greatest Common Divisor».
• Método para calcular o máximo divisor e o mínimo múltiplo comúns á vez Arquivado 01 de xuño de 2017 en Wayback Machine.