Ver o código fonte de «Máximo común divisor»

[[Ficheiro:24x60.svg|miniatura|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''.]]
En matemáticas, o '''máximo común divisor''' ('''MCD''' ou '''mdc''')<ref>{{cita libro|título=Profesionaliza a túa lingua matemática|editorial=Univesidade da Coruña|nome1=Libia|apelidos1=Pérez Vázquez|nome2=Patricia|apelidos2=Precedo Estraviz|nome3=Nuria|apelidos3=Seoane Bouzas|data=2006|isbn=84-9749-226-9}}</ref> ou '''máximo divisor común'''<ref>{{cita libro|apelidos=Masa Vázquez|nome=Xosé M.|apelidos2=Fortes López|nome2=Belén|título=Vocabulario de Matemáticas|ano=1995|editor=Servicio de Normalización Lingüística da Universidade de Santiago de Compostela|localización=Santiago de Compostela|isbn=84-8121-369-1}}</ref> de dous ou máis [[Número enteiro|números enteiros]] é o maior número enteiro que os [[Divisor|divide]] sen deixar resto.

== Definicións ==
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''.<ref>Belski e Kaluzhin, ''División inexacta'' (1997). Editorial Científica, Lima; páx.10</ref> 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 [[Números primos entre si|primos entre si]].

Un número enteiro ''d'' chámase máximo común divisor dos números ''a'' e ''b'' cando:
# ''d'' é divisor común dos números ''a'' e ''b'' e
# ''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.<ref>Ibídem, páx. 10</ref>

== Cálculo do máximo divisor común ==
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 ===
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 [[Potenciación|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.
[[Ficheiro:Divisores_48_60.svg|dereita|200x200px]]
{|
|
:{|
| <math>
   \begin{array}{r|l}
      48 & 2  \\
      24 & 2  \\
      12 & 2  \\
       6 & 2  \\
       3 & 3  \\
       1 &  
   \end{array}
  </math>
|-
| <math>
   48 = 2^4 \cdot 3 \,
</math>
|}
|
:{|
| <math>
   \begin{array}{r|l}
      60 & 2  \\
      30& 2  \\
      15 & 3  \\
       5 & 5  \\
       1 &
   \end{array}
</math>
|-
| <math>
   60 = 2^2 \cdot 3 \cdot 5 \,
</math>
|}
|}

O mcd son os factores comúns co seu menor expoñente, isto é:
: <math>
   \operatorname{mcd} (48; 60) =
   2^2 \cdot 3 =
   12
</math>

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 ===
Un método máis eficiente é o [[algoritmo de Euclides]], que emprega o [[División euclidiana|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:
:<math>\operatorname{mcd}(a,0) = a</math>
:<math>\operatorname{mcd}(a,b) = \operatorname{mcd}(b, a \,\mathrm{mod}\, b).</math>

'''Exemplo 2''':
O MCD de 42 e 56 é 14. En efecto:
: <math>
   \operatorname{mcd}(42,56) = 14 \,
</math>

operando:
: <math>
   \frac{42}{14} = 3
   \; , \quad
   \frac{56}{14} = 4
</math>

=== Co mínimo múltiplo común ===
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'':
: <math>
   \operatorname{mcd}(a,b) =
   \frac{a\cdot b}{\operatorname{MCM}(a,b)}
</math>

=== MCD de tres ou máis números ===
O máximo común divisor de tres ou máis números pódese definir [[Recursividade|recursivamente]] empregando o método:
<math> \ \operatorname{mcd}(a,b,c) = \operatorname{mcd}(a, \operatorname{mcd}(b,c)) </math>.<ref>Vinogradov: Fundamentos de la teoría de números, editorial Mir.</ref><ref>Castellet, Álgebra lineal y geometría, tema I.</ref>

== Propiedades ==
1. Se <math>\ \operatorname{mcd}(a,b)=d</math> entón <math>\ \operatorname{mcd} \left(\frac{a}{d}, \frac{b}{d}\right)= 1 </math>  
2. Se <math>\ m</math> é un enteiro, <math>\ \operatorname{mcd}(ma,mb)= |m|\cdot \operatorname{mcd}(a,b)</math> 
3. Se <math>\ p</math> é un [[número primo]], entón <math>\ \operatorname{mcd}(p,m)=p</math> o bien <math>\ \operatorname{mcd}(m,p)=1</math>  
4. Se <math>d=\operatorname{mcd}(m,n),\ m=d'm'',\ n=d'n'',\ \operatorname{mcd}(m'',n'')=1</math>, entón <math>\ d=d' </math> 
5. Se <math>\ d'</math> é un divisor común de <math>\ m</math> e <math>\ n</math>, entón <math>d'\mid \operatorname{mcd}(m,n)</math>
6. Se <math>\ m=nq+r</math>, entón <math>\operatorname{mcd}(m,n)=\operatorname{mcd}(n,r)</math>
7. Se <math>\ 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</math>, entón <math> \operatorname{mcd}(m,n)=p_1^{\operatorname{min}(\alpha_1,\beta_1)}\cdots p_k ^ {\operatorname{min} (\alpha_k, \beta_k)} </math> 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.

[[Xeometría|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 ===
# Para calquera par de números enteiros ''a''≠0, ''b''≠0, existe un único mcd ''d'' ≥ 1.<ref>Ibídem, páx. 11</ref>
# 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''
# 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]]).
# 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 é [[Números primos entre si|coprimo]] cun deles, entón divide necesariamente o outro número ou factor.<ref name="Ibídem_1">Ibídem, páx. 13</ref>
# Cando un número ''a'' é coprimo cos números ''m'' e ''n'', tamén o é co produto ''mn''.
# (''a'', ''b'') é divisor de (''a'', ''bc'')<ref>Vorobiov: ''Números de Fibonacci'', Editorial Mir, Moscova (1974)</ref>
# ''t''(''a'', ''b'') = (''ta'', ''tb'') para todo ''t'' enteiro<ref>Enzo Gentile, Aritmética elemental, ediciones OEA</ref>
# Se (''m'', ''b'')= 1 entón (''am'', ''b'')= (''a'', ''b'')<ref>Gentile: Aritmética elemental OEA</ref>
# Se (''m'', ''b'')= 1, (''am'', ''n'') = 1 entón (''am'', ''bn'') = (''a'', ''b'')
# Para todo ''x'', (''a'', ''b'')= (''b'', ''a'') = (''a'', -''b'') = (''a'', ''b'' + ''ax'')<ref>Niven e Zuckerman: Teoría de los números</ref>
# Por definición, (0, 0) = 0;<ref>Gentile: Aritmética elemental</ref> deste xeito o mcd defínese en todo ℤ×ℤ.
# (''a'', ''b'') = ''b'' se e só se ''b''|''a'', (ou sexa se ''a'' é múltiplo de ''b'').
# Se (''a'', ''b'')= ''D'', entón (''an'', ''bn'') = ''Dn''<ref>Santillana: "Aritmética razonada", Lima</ref>
# ''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.<ref>Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)</ref>
# <math>(a^2, ab, b^2)= (a,b)^2</math><ref>Pódese comprobar tendo en conta que (''a''/''d'', ''b''/''d'')= 1, ''d''=MCD</ref>

=== MCD como operación interna ===
* 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''<ref>Cotlar-Sadosky: Introducción al álgebra. Eudeba, BS.</ref>
* 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'']<ref>Gentile: Ibídem</ref>
* Propiedade do [[un|1]]: (''a'', 1) = 1 para calquera enteiro ''a'', pois o 1 é divisor de todos os enteiros, ou ben xera os elementos de ℤ.

== Aplicacións ==
O mcd emprégase para simplificar [[Fracción (matemáticas)|fraccións]]. Por exemplo, para simplificar a fracción <math>\scriptstyle \frac {48}{60}</math> 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 <math>\scriptstyle \frac {4}{5} </math>.

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 <math>\scriptstyle \frac {48 \cdot 60}{12} = 240 </math>.

O mcd e o [[algoritmo de Euclides]] empréganse na resolución de [[Ecuación diofantiana|ecuacións diofánticas lineares]] con dúas incógnitas<ref>Ibídem páx. 17 y 20</ref> e para desenvolver un [[número racional]] en [[fracción continua|fraccións continuas]].<ref>Gentile: Aritmética elemental OEA (1987)</ref>

== Notas ==
{{listaref}}

== Véxase tamén ==
=== Bibliografía ===
*{{Cita libro|last=Andrews |first=George E. |author-link=George Andrews (mathematician) |year=1994 |origyear=1971 |title=Number Theory |publisher=Dover |publication-place= |page= |isbn=9780486682525 |url=https://books.google.com/books?id=eVwvvwZeBf4C |accessdate= }}
* [[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.&nbsp;856–862.
*{{Cita libro  | last1 = Hardy  | first1 = G. H. | author1-link = G. H. Hardy  | last2 = Wright | first2 = E. M. | author2-link = E. M. Wright  | title = An Introduction to the Theory of Numbers  | edition = Fifth  | publisher = [[Oxford University Press]]  | location = Oxford  | year = 1979  | 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.&nbsp;333–356.
* {{Cita libro| first = Calvin T. | last = Long | year = 1972 | title = Elementary Introduction to Number Theory | url = https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi | edition = 2nd | publisher = [[D. C. Heath and Company]] | location = Lexington | lccn = 77171950 }}
* {{Cita libro| first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | url = https://archive.org/details/elementsofnumber0000pett | publisher = [[Prentice Hall]] | location = Englewood Cliffs | 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."
=== Ligazóns externas ===
* Weisstein, Eric W. [http://mathworld.wolfram.com/GreatestCommonDivisor.html «Greatest Common Divisor».]
* [http://www.matalasmates.es/mcd-y-mcm-2-pajaros-de-un-tiro/ Método para calcular o máximo divisor e o mínimo múltiplo comúns á vez] {{Webarchive|url=https://web.archive.org/web/20170601054559/http://www.matalasmates.es/mcd-y-mcm-2-pajaros-de-un-tiro/ |date=01 de xuño de 2017 }}

{{Control de autoridades}}

[[Categoría:Teoría de números]]