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.

Rectángulo 24×60 recuberto con dez baldosas cadradas de 12×12, onde 12 é o mcd de 24 e 60. En xeral, un rectángulo a×b pode recubrirse con baldosas cadradas de lado c só se c é un divisor común de a e b.

Definicións

editar

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]

Cálculo do máximo divisor común

editar

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

Por descomposición en factores primos

editar

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

 

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.

Algoritmo de Euclides

editar

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:

 
 

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

 

operando:

 

Co mínimo múltiplo común

editar

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:

 

MCD de tres ou máis números

editar

O máximo común divisor de tres ou máis números pódese definir recursivamente empregando o método:  .[5][6]

Propiedades

editar

1. Se   entón   2. Se   é un enteiro,   3. Se   é un número primo, entón   o bien   4. Se  , entón   5. Se   é un divisor común de   e  , entón   6. Se  , entón   7. Se  , entón   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).

Proposicións

editar
  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.  [16]

MCD como operación interna

editar
  • 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 ℤ.

Aplicacións

editar

O mcd emprégase para simplificar fraccións. Por exemplo, para simplificar a fracción   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  .

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  .

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]

  1. Pérez Vázquez, Libia; Precedo Estraviz, Patricia; Seoane Bouzas, Nuria (2006). Profesionaliza a túa lingua matemática. Univesidade da Coruña. ISBN 84-9749-226-9. 
  2. Masa Vázquez, Xosé M.; Fortes López, Belén (1995). Servicio de Normalización Lingüística da Universidade de Santiago de Compostela, ed. Vocabulario de Matemáticas. Santiago de Compostela. ISBN 84-8121-369-1. 
  3. Belski e Kaluzhin, División inexacta (1997). Editorial Científica, Lima; páx.10
  4. Ibídem, páx. 10
  5. Vinogradov: Fundamentos de la teoría de números, editorial Mir.
  6. Castellet, Álgebra lineal y geometría, tema I.
  7. Ibídem, páx. 11
  8. Ibídem, páx. 13
  9. Vorobiov: Números de Fibonacci, Editorial Mir, Moscova (1974)
  10. Enzo Gentile, Aritmética elemental, ediciones OEA
  11. Gentile: Aritmética elemental OEA
  12. Niven e Zuckerman: Teoría de los números
  13. Gentile: Aritmética elemental
  14. Santillana: "Aritmética razonada", Lima
  15. Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)
  16. Pódese comprobar tendo en conta que (a/d, b/d)= 1, d=MCD
  17. Cotlar-Sadosky: Introducción al álgebra. Eudeba, BS.
  18. Gentile: Ibídem
  19. Ibídem páx. 17 y 20
  20. Gentile: Aritmética elemental OEA (1987)

Véxase tamén

editar

Bibliografía

editar

Ligazóns externas

editar