Máximu común divisor
Nes [[matemátiques]], defínese'l '''máximu común divisor''' (embrivíu '''MCD''') de dos o más [[Númberu enteru|númberos enteros]] al mayor númberu enteru que los [[División (matemátiques)|divide]]. Pa dos enteros cualesquier; ''x'', ''y'', el máximu común divisor de ''x'' ya ''y'' denotase <math>mcd(x, y)</math>.

== Descripción ==
Daos <chem>a</chem> y <math>b</math> dos númberos enteros distintos de [[cero]]. Si un númberu <math>c</math> divide a <math>a</math> y <math>b</math>, esto ye, <math>c|a</math> y <math>c|b</math>, vamos dicir que <math>c</math> ye divisor común de <math>a</math> y <math>b</math>.<ref>«División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10</ref> Observése que dos númberos enteros cualesquier tienen divisores comunes. 

Polo tanto podemos dar una primer definición de máximu común divisor, ya que dicimos que ''d'' ye máximu común divisor si verificáse que:

# ''d'' ye divisor común de los númberos ''a'' y ''b''
# ''d'' ye divisible por cualesquier otru divisor común de los númberos ''a'' y ''b''.

=== Exemplu ===
''¿Cuál ye'l máximu común divisor de 54 y 24?''

El númberu 54 puede espresáse cómo productu de númberos enteros de les siguientes maneres:

<math>54= 54 \times1=27\times 2=18\times 3= 9 \times 6</math>

Asina, los '''divisores de 54''' son <math>1,2,3,6,9,18,27,54</math>.

Análogamente los '''divisores de 24''' son <math>1, 2, 3,4,6,8,12,24</math>.

Los númberos qu'apaecen en dambes llistes son '''cómunes divisores''' de 54 y 24:

<math>1,2,3,6</math>

El mayor númberu d'esos ye por tanto en '''máximu cómun divisor''' de 54 y 24:

<math>mcd(54, 24)=6</math>

=== Númberos primos ente sí ===
Cuando'l máximu común divisor de dos númberos ye 1, dizse qu'estos son primos ente sí o [[Númberos coprimos|coprimos]].

=== Interpretación xeométrica ===
[[Ficheru:24x60.svg|miniaturadeimagen|Un rectángulu de 24 por 60 ta cubiertu con diez cuadraos de 12 por 12, onde 12 ye'l MCD de 24 y 60. Más xeneralmente, un rectángulu de a por b puede ser cubiertu con cuadraos de llau c namás si c ye'l mínimu común divisor de a y b.]]
Por exemplu, un área rectangular de 24 por 60 pue ser dividía por una malla de cuadraos de: 1 por 1 , 2 por 2, 3 por 3, 4 por 4, 6 por 6 o 12 por 12. Por tanto, 12 ye'l máximu común divisor de 24 y 60. Un área rectangular 24 por 60 asina pue ser dividía por una malla de cuadraos de 12 por 12, con dos cuadraos a lo llargo d'un llau (24/12=2) y cinco cuadraos a lo llargo del otru (60/12=5). 

== Cálculu del Máximu Común Divisor ==

=== Por descomposición en factores primos ===
El máximu común divisor de dos númberos puede calculase determinando la [[Teorema fundamental de l'aritmética|descomposición en factores primos]] de los dos númberos y tomando los factores comunes elevaos a la menor potencia, el productu de los cualos va ser el MCD.

Exemplu: para calcular el máximu común divisor de 48 y de 60 facemos la so factorización en factores primos.
[[Ficheru:Divisores_48_60.svg|derecha|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>
|}
|}
El MCD son los factores comunes col so menor esponente, esto ye:

: <math>
 \operatorname{MCD} (48; 60) =
 2^2 \cdot 3 =
 12
</math>

Na práctica, esti métodu solo ye operativu para númberos pequeños tomando polo xeneral demasiáu tiempu calcular la descomposición en factores primos de dos númberos cualesquier.

=== Usando l'algoritmu de Euclides ===
{{AP|Algoritmu d'Euclides}}
Un métodu más eficiente ye l'algoritmu de Euclides, qu'utiliza l'algoritmu de la división xunto al fechu que'l MCD de dos númberos tamién estrema al restu llográu d'estremar el mayor ente'l más pequeñu.

===== Exemplu 1: =====
Si se divide 60 ente 48 dando un cociente de 1 y un restu de 12, el MCD va ser por tanto divisor de 12. Dempués estrémase 48 ente 12 dando un restu de 0, lo que significa que 12 ye'l MCD. Formalmente puede describise como:

<math>\operatorname{mcd}(a,0) = a</math>

<math>\operatorname{mcd}(a,b) = \operatorname{mcd}(b, a \,\mathrm{mod}\, b).</math>

'''Exemplu 2:'''

El MCD de 42 y 56 ye 14. N'efectu:

<math>
 \operatorname{mcd}(42,56) = 14 \,
</math>

operando:

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

=== Usando'l mínimu común múltiplu ===
El máximu común divisor tamién pue ser calculáu usando'l [[mínimu común múltiplu]]. Si ''a'' y ''b'' son distintos de [[cero]], entós el máximu común divisor de ''a'' y ''b'' llograse por aciu la siguiente fórmula, qu'arreya'l mínimu común múltiplu de ''a'' y ''b'':

<math>
 \operatorname{MCD}(a,b) =
 \frac{a\cdot b}{\operatorname{mcm}(a,b)}
</math>

=== MCD de trés o más númberos ===
El máximu común divisor de trés o más númberos puede definise usando recursivamente: <math> \ \operatorname{MCD}(a,b,c) = \operatorname{MCD}(a, \operatorname{MCD}(b,c)) </math><ref>Vinogradov: Fundamentos de la teoría de númberos, editorial mir.</ref><ref>Castellet, Álgebra lineal y geometría, tema I.</ref>

== Propiedaes ==

# Si <math>\ \operatorname{mcd}(a,b)=d</math> entós <math>\ \operatorname{mcd} \left(\frac{a}{d}, \frac{b}{d}\right)= 1 </math>
# Si <math>\ m\in\mathbb{Z}</math>, <math>\ \operatorname{mcd}(ma,mb)= |m|\cdot \operatorname{mcd}(a,b)</math>
# Si <math>\ p</math> ye un númberu primu, entós <math>\ \operatorname{mcd}(p,m)=p</math> o bien <math>\ \operatorname{mcd}(m,p)=1</math>
# Si <math>d=\operatorname{mcd}(m,n),\ m=d'm'',\ n=d'n'',\ \operatorname{mcd}(m'',n'')=1</math>, entós <math>\ d=d' </math>
# Si <math>\ d'</math> ye un divisor común de <math>\ m</math> y <math>\ n</math>, entós <math>d'\mid \operatorname{mcd}(m,n)</math>
# Si <math>\ m=nq+r</math>, entós <math>\operatorname{mcd}(m,n)=\operatorname{mcd}(n,r)</math>
# Si <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ós:

: <math> \operatorname{mcd}(m,n)=p_1^{\operatorname{min}(\alpha_1,\beta_1)}\cdots p_k ^ {\operatorname{min} (\alpha_k, \beta_k)} </math>

La última propiedá indica que'l máximu común divisor de dos númberos resulta ser el productu de los sos factores primos comunes elevaos al menor esponente.

[[Xeometría|Xeométricamente]], el máximu común divisor de ''a'' y ''b'' ye'l númberu de puntos de coordenaes enteres qu'hai nel segmentu que xune los puntos (0,0) y (a,b), escluyendo'l (0,0).

=== Proposiciones ===

# <math>\forall\ a,\ b\in\mathbb{Z}</math> <math>\ni</math> <math> \ a,\ b \neq \ 0</math> , <math>\exists !</math>d ≥ 1 <math>\ni</math> MCD(a, b) = d.<ref>Ibídem, pg. 11</ref>
# El m.c.d. de los númberos a y b puede ser representáu en forma de combinación llineal d'estos númberos. Esto ye (a, b) = ax + by
# Si dos númberos enteros son [[Númberos coprimos|primos ente sí]], i.e. el so mcd = 1 o n'otra notación (a,b) = 1, entós cabo la representación ma + nb = 1 onde m y n son númberos enteros ([[Identidá de Bézout]]).
# Si a|bc y (a,b) = 1, va ser a|c. N'otres palabres, si un númberu ''a'' divide un productu d'otros dos númberos y ye coprimo con unu d'ellos, entós divide necesariamente l'otru númberu o factor.
# MCD(''a, m) = 1'' <math>\land</math> MCD(''a, n) = 1'' <math>\Longrightarrow</math> MCD( a, ''mn) = 1''.<ref name="Ibídem_1">Ibídem, pg. 13</ref>
# (a,b) ye divisor de (a, bc)<ref>Vorobiov: Números de Fibonacci, Editorial Mr, Moscú (1974)</ref>
# t(a,b) = (ta, tb) para tou t entero<ref>Enzo gentile, Aritmética elemental, ediciones OEA</ref>
# Si (m, b)= 1 entós (am, b)= (a, b)<ref>Gentile: Aritmética elemental OEA</ref>
# Si (m,b)= 1, (am, n) = 1 entós (am, bn) = (a, b)
# Para tou x, (a, b)= (b, a) = (a, -b) = (a, b + ax)<ref>Niven y Zuckerman: Teoría de los números</ref>
# " Por definición, (0, 0) = 0 ".<ref>Gentile: Aritmética elemental</ref> De tal manera'l mcd definiriase en tou ℤxℤ.
# (a, b) = b si sólo si b | a, ( O sea si a es múltiplo de b).
# Si (a,b)= D, entós (a<sup>n</sup>, b<sup>n</sup>) = D<sup>n</sup>
# mZ + nZ = (m,n)Z. Si sumemos dos talos múltiplos de dos enteros ye lo mesmo que considerar los múltiplos del so máximu común divisor.<ref>Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)</ref>
# <math>(a^2, ab, b^2)= (a,b)^2</math>

=== MCD como operación interna ===

* El MCD puédese estructurar como una operación en ℤ, d'esta miente a cualquier par d'enteros, esto ye a un elementu de ℤ asígna-y un únicu elementu de ℤ.
* Para cualquier par d'enteros (a,b) esiste un enteru non negativu ''d'' que ye'l so máximu común divisor. Esto ye ab = (a,b) = d
* El MCD gocia de la propiedá asociativa, como de la propiedá conmutativa.
* El MCD tien un elementu identidá, el cero, de manera tal que (a, 0)= (0,a)= a<ref>Cotlar- Sadosky: Introducción al álgebra Eudeba, BS. As</ref>
* El MCD tien un comportamientu dual que'l mínimu común múltiplu y a los enteros non negativos a y b amestalos la ecuación ab = (a,b)[a,b]<ref>Gentile: Ibídem</ref>
* Propiedá de 1: (a,1) = 1 para cualesquier enteru a.

== Aplicaciones ==
El mcd utilízase para simplificar [[Fraición|fraiciones]]. Por exemplu, pa simplificar la fraición <math>\scriptstyle \frac {48}{60}</math> calcúlase primero'l mcd(60, 48) = 12, dividiendose'l numberador y el denominador de la fracción inicial por 12 para llograr la fracción simplificada <math>\scriptstyle \frac {4}{5} </math>.

El mcd tamién s'utiliza pa calcular el mínimu común múltiplu de dos númberos. N'efectu, el productu de los dos númberos ye igual al productu del so máximu común divisor pol so mínimu común múltiplu. Asina, para calcular el mínimu común múltiplu de 48 y de 60, calculamos primero'l so mcd, 12, siendo'l so mínimu común múltiplu <math>\scriptstyle \frac {48 \cdot 60}{12} = 240 </math>.

El mcd y l'[[Algoritmu d'Euclides|algoritmu de Euclides]] emplegase nel resolvimientu d'[[Ecuación diofántica|ecuaciones diofánticas llineales]] con dos incógnites.<ref>Ibídem pg. 17 y 20</ref>

L'algoritmu de Euclides emplegase nel desenvolvimientu d'un númberu racional en fracción siguida (sic)<ref>Gentile: Aritmética elemental OEA (1987)</ref>

== Ver tamién ==

* [[Mínimu común múltiplu|Mínimu común múltiplo]]
* [[Númberos coprimos|Númberos primos ente sí]]

== Referencies ==
{{Llistaref}}
{{Control d'autoridaes}}

[[Categoría:Aritmética elemental]]
Nes matemátiques, defínese'l máximu común divisor (embrivíu MCD) de dos o más númberos enteros al mayor númberu enteru que los divide. Pa dos enteros cualesquier; x, y, el máximu común divisor de x ya y denotase .

 Descripción 
Daos a y  dos númberos enteros distintos de cero. Si un númberu  divide a  y , esto ye,  y , vamos dicir que  ye divisor común de  y .«División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10 Observése que dos númberos enteros cualesquier tienen divisores comunes. 

Polo tanto podemos dar una primer definición de máximu común divisor, ya que dicimos que d ye máximu común divisor si verificáse que:

 d ye divisor común de los númberos a y b
 d ye divisible por cualesquier otru divisor común de los númberos a y b.

 Exemplu 
¿Cuál ye'l máximu común divisor de 54 y 24?

El númberu 54 puede espresáse cómo productu de númberos enteros de les siguientes maneres:

Asina, los divisores de 54 son .

Análogamente los divisores de 24 son .

Los númberos qu'apaecen en dambes llistes son cómunes divisores de 54 y 24:

El mayor númberu d'esos ye por tanto en máximu cómun divisor de 54 y 24:

 Númberos primos ente sí 
Cuando'l máximu común divisor de dos númberos ye 1, dizse qu'estos son primos ente sí o coprimos.

 Interpretación xeométrica 
miniaturadeimagen|Un rectángulu de 24 por 60 ta cubiertu con diez cuadraos de 12 por 12, onde 12 ye'l MCD de 24 y 60. Más xeneralmente, un rectángulu de a por b puede ser cubiertu con cuadraos de llau c namás si c ye'l mínimu común divisor de a y b.
Por exemplu, un área rectangular de 24 por 60 pue ser dividía por una malla de cuadraos de: 1 por 1 , 2 por 2, 3 por 3, 4 por 4, 6 por 6 o 12 por 12. Por tanto, 12 ye'l máximu común divisor de 24 y 60. Un área rectangular 24 por 60 asina pue ser dividía por una malla de cuadraos de 12 por 12, con dos cuadraos a lo llargo d'un llau (24/12=2) y cinco cuadraos a lo llargo del otru (60/12=5). 

 Cálculu del Máximu Común Divisor 

 Por descomposición en factores primos 
El máximu común divisor de dos númberos puede calculase determinando la descomposición en factores primos de los dos númberos y tomando los factores comunes elevaos a la menor potencia, el productu de los cualos va ser el MCD.

Exemplu: para calcular el máximu común divisor de 48 y de 60 facemos la so factorización en factores primos.
derecha|200x200px
 {|
|
 {|
|
|-
|
|}
|}
El MCD son los factores comunes col so menor esponente, esto ye:

 

Na práctica, esti métodu solo ye operativu para númberos pequeños tomando polo xeneral demasiáu tiempu calcular la descomposición en factores primos de dos númberos cualesquier.

 Usando l'algoritmu de Euclides 

Un métodu más eficiente ye l'algoritmu de Euclides, qu'utiliza l'algoritmu de la división xunto al fechu que'l MCD de dos númberos tamién estrema al restu llográu d'estremar el mayor ente'l más pequeñu.

 Exemplu 1: 
Si se divide 60 ente 48 dando un cociente de 1 y un restu de 12, el MCD va ser por tanto divisor de 12. Dempués estrémase 48 ente 12 dando un restu de 0, lo que significa que 12 ye'l MCD. Formalmente puede describise como:

Exemplu 2:

El MCD de 42 y 56 ye 14. N'efectu:

operando:

 Usando'l mínimu común múltiplu 
El máximu común divisor tamién pue ser calculáu usando'l mínimu común múltiplu. Si a y b son distintos de cero, entós el máximu común divisor de a y b llograse por aciu la siguiente fórmula, qu'arreya'l mínimu común múltiplu de a y b:

 MCD de trés o más númberos 
El máximu común divisor de trés o más númberos puede definise usando recursivamente: Vinogradov: Fundamentos de la teoría de númberos, editorial mir.Castellet, Álgebra lineal y geometría, tema I.

 Propiedaes 

 Si  entós 
 Si , 
 Si  ye un númberu primu, entós  o bien 
 Si , entós 
 Si  ye un divisor común de  y , entós 
 Si , entós 
 Si , entós:

 

La última propiedá indica que'l máximu común divisor de dos númberos resulta ser el productu de los sos factores primos comunes elevaos al menor esponente.

Xeométricamente, el máximu común divisor de a y b ye'l númberu de puntos de coordenaes enteres qu'hai nel segmentu que xune los puntos (0,0) y (a,b), escluyendo'l (0,0).

 Proposiciones 

    , d ≥ 1  MCD(a, b) = d.Ibídem, pg. 11
 El m.c.d. de los númberos a y b puede ser representáu en forma de combinación llineal d'estos númberos. Esto ye (a, b) = ax + by
 Si dos númberos enteros son primos ente sí, i.e. el so mcd = 1 o n'otra notación (a,b) = 1, entós cabo la representación ma + nb = 1 onde m y n son númberos enteros (Identidá de Bézout).
 Si a|bc y (a,b) = 1, va ser a|c. N'otres palabres, si un númberu a divide un productu d'otros dos númberos y ye coprimo con unu d'ellos, entós divide necesariamente l'otru númberu o factor.
 MCD(a, m) = 1  MCD(a, n) = 1  MCD( a, mn) = 1.Ibídem, pg. 13
 (a,b) ye divisor de (a, bc)Vorobiov: Números de Fibonacci, Editorial Mr, Moscú (1974)
 t(a,b) = (ta, tb) para tou t enteroEnzo gentile, Aritmética elemental, ediciones OEA
 Si (m, b)= 1 entós (am, b)= (a, b)Gentile: Aritmética elemental OEA
 Si (m,b)= 1, (am, n) = 1 entós (am, bn) = (a, b)
 Para tou x, (a, b)= (b, a) = (a, -b) = (a, b + ax)Niven y Zuckerman: Teoría de los números
 " Por definición, (0, 0) = 0 ".Gentile: Aritmética elemental De tal manera'l mcd definiriase en tou ℤxℤ.
 (a, b) = b si sólo si b | a, ( O sea si a es múltiplo de b).
 Si (a,b)= D, entós (an, bn) = Dn
 mZ + nZ = (m,n)Z. Si sumemos dos talos múltiplos de dos enteros ye lo mesmo que considerar los múltiplos del so máximu común divisor.Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)
 

 MCD como operación interna 

 El MCD puédese estructurar como una operación en ℤ, d'esta miente a cualquier par d'enteros, esto ye a un elementu de ℤ asígna-y un únicu elementu de ℤ.
 Para cualquier par d'enteros (a,b) esiste un enteru non negativu d que ye'l so máximu común divisor. Esto ye ab = (a,b) = d
 El MCD gocia de la propiedá asociativa, como de la propiedá conmutativa.
 El MCD tien un elementu identidá, el cero, de manera tal que (a, 0)= (0,a)= aCotlar- Sadosky: Introducción al álgebra Eudeba, BS. As
 El MCD tien un comportamientu dual que'l mínimu común múltiplu y a los enteros non negativos a y b amestalos la ecuación ab = (a,b)[a,b]Gentile: Ibídem
 Propiedá de 1: (a,1) = 1 para cualesquier enteru a.

 Aplicaciones 
El mcd utilízase para simplificar fraiciones. Por exemplu, pa simplificar la fraición  calcúlase primero'l mcd(60, 48) = 12, dividiendose'l numberador y el denominador de la fracción inicial por 12 para llograr la fracción simplificada .

El mcd tamién s'utiliza pa calcular el mínimu común múltiplu de dos númberos. N'efectu, el productu de los dos númberos ye igual al productu del so máximu común divisor pol so mínimu común múltiplu. Asina, para calcular el mínimu común múltiplu de 48 y de 60, calculamos primero'l so mcd, 12, siendo'l so mínimu común múltiplu .

El mcd y l'algoritmu de Euclides emplegase nel resolvimientu d'ecuaciones diofánticas llineales con dos incógnites.Ibídem pg. 17 y 20

L'algoritmu de Euclides emplegase nel desenvolvimientu d'un númberu racional en fracción siguida (sic)Gentile: Aritmética elemental OEA (1987)

 Ver tamién 

 Mínimu común múltiplo
 Númberos primos ente sí

 Referencies 

Categoría:Aritmética elemental