Màxim comú divisor

En les matemàtiques, es definix el màxim comú divisor (mcd o m.Plantilla:Nbspc.Plantilla:Nbspd.) de dos o més número entero al major número entero que els dividix sense deixar residu algun.

Precisió

El $a$ i $b$ dos número entero distints de zero. Si un número $c$ dividix a $a$ i $b$, és dir, $c|a$ i $c|b$, direm que $c$ és divisor comú de $a$ i $b$. Observe's que dos número entero qualssevol tenen divisores comuns. Si els divisores comuns de $a$ i $b$ són únicament 1 i -1 llavors direm són cosins entre sí'.

Un número entero d es diu màxim comú divisor (M.C.D) dels números a i b quan:

1. d és divisor comuna dels números a i b
2. d és divisible per qualsevol atre divisor comú dels números a i b.

Eixemple:

12 és el mcd de 36 i 60. Puix 12|36 i 12|60; a la seua volta 12 és divisible per 1, 2, 3, 4, 6 i 12 que són divisores comuns de 36 i 60.

Càlcul del màxim comú divisor

Els tres métodos més utilisats per al càlcul del màxim comú divisor de dos números són:

Per descomposició en factors primers

Artícul principal → Factorización de sancers.

El màxim comú divisor de dos números pot calcular-se determinant la descomposició en factors primers dels dos números i prenent els factors comuns elevats a la menor potència, el producte dels quals serà el MCD.

Eixemple: per a calcular el màxim comú divisor de 48 i de 60 s'obté de la seua factorización en factors primers.

Archiu:Divisores 48 60.svg

$\begin{array}{cc}48& 2\\ 24& 2\\ 12& 2\\ 6& 2\\ 3& 3\\ 1& \end{array}$ $48=2^4\cdot 3$

$\begin{array}{cc}60& 2\\ 30& 2\\ 15& 3\\ 5& 5\\ 1& \end{array}$ $60=2^2\cdot 3\cdot 5$

El MCD són els factors comuns en el seu menor exponent, açò és:

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

En la pràctica, este método solament és operatiu per a números menuts prenent en general massa temps calcular la descomposició en factors primers de dos números qualssevol.

Usant l'algoritme de Euclides

Artícul principal → Algoritme de Euclides.

Un método més eficient és l'algoritme de Euclides, que utilisa l'algoritme de la divisió junt al fet que el MCD de dos números també dividix al restant obtingut de dividir el major entre el més menut.

Eixemple 1:

Si es dividix 60 entre 48 donant un cocient d'1 i un restant de 12, el MCD serà per tant divisor de 12. Despuix es dividix 48 entre 12 donant un restant de 0, lo que significa que 12 és el MCD. Formalment pot descriure's com:

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

$\mathrm{mcd}(a,b)=\mathrm{mcd}(b,a\mathrm{m}\mathrm{o}\mathrm{d}b).$

Eixemple 2:

El MCD de 42 i 56 és 14. En efecte:

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

operant:

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

Usant el mínim comú múltiple

El màxim comú divisor també pot ser calculat usant el mínim comú múltiple. Si a i b són distints de zero, llavors el màxim comú divisor de a i b s'obté per mig de la següent fòrmula, que involucra el mínim comú múltiple de a i b:

$\mathrm{MCD}(a,b)=\frac{a\cdot b}{\mathrm{mcm}(a,b)}$

MCD de tres o més números

El màxim comú divisor de tres o més números es pot definir usant recursivamente: $\mathrm{MCD}(a,b,c)=\mathrm{MCD}(a,\mathrm{MCD}(b,c))$.

Propietats

1. Si $\mathrm{MCD}(a,b)=d$ llavors $\mathrm{MCD}(\frac{a}{d},\frac{b}{d})=1$
2. Si $m\in \mathbb{Z}$, $\mathrm{MCD}(ma,mb)=|m|\cdot \mathrm{MCD}(a,b)$
3. Si $p$ és un número primo, llavors $\mathrm{MCD}(p,m)=p$ o be $\mathrm{MCD}(m,p)=1$
4. Si $d=\mathrm{MCD}(m,n),m=d^{\prime }{m}^{″},n=d^{\prime }{n}^{″},\mathrm{MCD}(m^{″},n^{″})=1$, llavors $d=d^{\prime }$
5. Si $d^{\prime }$ és un divisor comú de $m$ i $n$, llavors $d^{\prime }\mid \mathrm{MCD}(m,n)$
6. Si $m=nq+r$, llavors $\mathrm{MCD}(m,n)=\mathrm{MCD}(n,r)$
7. 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\ge 0,i=1,\mathrm{...},k$, llavors:

$\mathrm{MCD}(m,n)=p_1^{\min ({\alpha }_1,{\beta }_1)}\cdots p_k^{\min ({\alpha }_k,{\beta }_k)}$

L'última propietat indica que el màxim comú divisor de dos números resulta ser el producte dels seus factors primers comuns elevats al menor exponent.

Geomètricament, el màxim comú divisor de a i b és el número de punts de coordenades sanceres que hi ha en el segment que unix els punts (0,0) i (a,b), excloent el (0,0).

Proposicions

1. $\mathrm{\forall }a,b\in \mathbb{Z}$ $\ni$ $a,b\ne 0$ , $\mathrm{\exists }!$d ≥ 1 $\ni$ MCD(a, b) = d.
2. El M.C.D. dels números a i b pot ser representat en forma de combinació llineal d'estos números. Açò és (a, b) = ax + by
3. Si dos número entero són cosins entre sí, i.i. el seu MCD = 1 o en una atra notació (a,b) = 1, llavors cap la representació ma + nb = 1 a on m i n són número entero (Identitat de Bézout).
4. si a|bc i (a,b) = 1, serà a|c. En atres paraules, si un número a dividix un producte d'atres dos números i és coprimo en un d'ells, llavors dividix necessàriament l'atre número o factor.
5. MCD(a, m) = 1 $\wedge$ MCD(a, n) = 1 $⟹$ MCD( a, mn) = 1.
6. (a,b) és divisor de (a, bc)
7. t(a,b) = (ta, tb) para tot t sancer
8. Si (m, b)= 1 llavors (am, b)= (a, b)
9. Si (m,b)= 1, (am, n) = 1 llavors (am, bn) = (a, b)
10. Para tot x, (a, b)= (b, a) = (a, -b) = (a, b + ax)
11. " Per definició, (0, 0) = 0 ". De tal modo el mcd es definiria en tot ℤxℤ.
12. (a, b) = b si solament si b | a, ( O siga si a és múltiple de b).
13. Si (a,b)= D, llavors (aⁿ, bⁿ) = Dⁿ
14. mZ + nZ = (m,n)Z. Si vàrem sumar sengles múltiples de dos sancers és lo mateix que considerar els múltiples del seu màxim comú divisor.
15. $(a^2,ab,b^2)=(a,b{)}^2$

MCD com a operació interna

• EL MCD es pot estructurar com una operació en Z, d'esta manera a qualsevol parell de sancers, o siga a un element de Z x Z, li assigna un únic element de Z
• Per a qualsevol parell de sancers (a,b) existix un sancer no negatiu d que és el seu màxim comú divisor. Açò és ab = (a,b) = d
• El MCD goja de la propietat associativa, com de la propietat conmutativa.
• El MCD posseïx un element identitat, el zero, de modo tal que (a, 0)= (0,a)= a
• El MCD té un comportament dual que el mínim comú múltiple i als sancers no negatius a i b els lliga l'equació ab = (a,b)[a,b]
• Propietat d'1: (a,1) = 1 per a qualsevol sancer a

Aplicacions

El MCD s'utilisa per a simplificar fracciones. Per eixemple, per a simplificar la fracció $\frac{48}{60}$ es calcula primer el mcd(60, 48) = 12, dividint-se el numerador i el denominador de la fracció inicial per 12 per a obtindre la fracció simplificada $\frac{4}{5}$.

El MCD també s'utilisa per a calcular el mínim comú múltiple de dos números. En efecte, el producte dels dos números és igual al producte del seu màxim comú divisor pel seu mínim comú múltiple. Aixina, per a calcular el mínim comú múltiple de 48 i de 60, calculem primer el seu mcd, 12, sent el seu mínim comú múltiple $\frac{48\cdot 60}{12}=240$.

El MCD i l'algoritme de Euclides s'ampra en la resolució d'equacions diofánticas llineals en dos incògnites.

L'algoritme de Euclides s'ampra en el desenroll d'un número racional en fracció continuada (sic).

Vore també

• Mínim comú múltiple
• Número primo entre sí