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ú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 $mcd(x,y)$ .

Descripción

Daos ${\ce {a}}$ y $b$ dos númberos enteros distintos de cero. Si un númberu $c$ divide a $a$ y $b$ , esto ye, $c|a$ y $c|b$ , vamos dicir que $c$ ye divisor común de $a$ y $b$ .^[1] 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:

$54=54\times 1=27\times 2=18\times 3=9\times 6$

Asina, los divisores de 54 son $1,2,3,6,9,18,27,54$ .

Análogamente los divisores de 24 son $1,2,3,4,6,8,12,24$ .

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

$1,2,3,6$

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

$mcd(54,24)=6$

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

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.

{\begin{array}{r|l}48&2\\24&2\\12&2\\6&2\\3&3\\1&\end{array}}

48=2^{4}\cdot 3\,

{\begin{array}{r|l}60&2\\30&2\\15&3\\5&5\\1&\end{array}}

60=2^{2}\cdot 3\cdot 5\,

El MCD son los factores comunes col so menor esponente, esto ye:

\operatorname {MCD} (48;60)=2^{2}\cdot 3=12

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:

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

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

Exemplu 2:

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

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

operando:

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

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:

$\operatorname {MCD} (a,b)={\frac {a\cdot b}{\operatorname {mcm} (a,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: $\ \operatorname {MCD} (a,b,c)=\operatorname {MCD} (a,\operatorname {MCD} (b,c))$ ^[2]^[3]

Propiedaes

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

\operatorname {mcd} (m,n)=p_{1}^{\operatorname {min} (\alpha _{1},\beta _{1})}\cdots p_{k}^{\operatorname {min} (\alpha _{k},\beta _{k})}

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

$\forall \ a,\ b\in \mathbb {Z}$ $\ni$ $\ a,\ b\neq \ 0$ , $\exists !$ d ≥ 1 $\ni$ MCD(a, b) = d.^[4]
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 $\land$ MCD(a, n) = 1 $\Longrightarrow$ MCD( a, mn) = 1.^[5]
(a,b) ye divisor de (a, bc)^[6]
t(a,b) = (ta, tb) para tou t entero^[7]
Si (m, b)= 1 entós (am, b)= (a, b)^[8]
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)^[9]
" Por definición, (0, 0) = 0 ".^[10] 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ⁿ, bⁿ) = Dⁿ
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.^[11]
$(a^{2},ab,b^{2})=(a,b)^{2}$

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^[12]
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]^[13]
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 $\scriptstyle {\frac {48}{60}}$ 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 $\scriptstyle {\frac {4}{5}}$ .

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

El mcd y l'algoritmu de Euclides emplegase nel resolvimientu d'ecuaciones diofánticas llineales con dos incógnites.^[14]

L'algoritmu de Euclides emplegase nel desenvolvimientu d'un númberu racional en fracción siguida (sic)^[15]

Ver tamién

Referencies

↑ «División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10
↑ Vinogradov: Fundamentos de la teoría de númberos, editorial mir.
↑ Castellet, Álgebra lineal y geometría, tema I.
↑ Ibídem, pg. 11
↑ Ibídem, pg. 13
↑ Vorobiov: Números de Fibonacci, Editorial Mr, Moscú (1974)
↑ Enzo gentile, Aritmética elemental, ediciones OEA
↑ Gentile: Aritmética elemental OEA
↑ Niven y Zuckerman: Teoría de los números
↑ Gentile: Aritmética elemental
↑ Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)
↑ Cotlar- Sadosky: Introducción al álgebra Eudeba, BS. As
↑ Gentile: Ibídem
↑ Ibídem pg. 17 y 20
↑ Gentile: Aritmética elemental OEA (1987)

[1] «División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10

[2] Vinogradov: Fundamentos de la teoría de númberos, editorial mir.

[3] Castellet, Álgebra lineal y geometría, tema I.

[4] Ibídem, pg. 11

[Ibídem_1-5] Ibídem, pg. 13

[6] Vorobiov: Números de Fibonacci, Editorial Mr, Moscú (1974)

[7] Enzo gentile, Aritmética elemental, ediciones OEA

[8] Gentile: Aritmética elemental OEA

[9] Niven y Zuckerman: Teoría de los números

[10] Gentile: Aritmética elemental

[11] Kostrikin: Introducción al álgebra, Editorial Mir, Moscú (1974)

[12] Cotlar- Sadosky: Introducción al álgebra Eudeba, BS. As

[13] Gentile: Ibídem

[14] Ibídem pg. 17 y 20

[15] Gentile: Aritmética elemental OEA (1987)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]