# Màxim comú divisor

El màxim comú divisor (mcd) de dos o més nombres enters és, a excepció del signe, el major divisor possible de tots ells. Si el màxim comú divisor de dos nombres és 1, aleshores aquests nombres es diuen coprimers o primers entre ells. Si no hi ha cap divisor comú, es diu que són primers entre ells.

## Generalitats

* Tot i que podem anar provant nombres naturals un per un fins a trobar el m.c.d., existeix un mètode general per trobar-lo. Consisteix a descompondre tots els nombres en factors primers i només agafem els comuns al menor exponent. Multiplicant aquests factors comuns trobem el màxim comú divisor.
Exemple: per calcular el màxim comú divisor de 6936 i de 1200 s'obté de la seva factorització en factors primers
| ${\begin{array}{r|l}6936&2\\3468&2\\1734&2\\867&3\\289&17\\17&17\\1&\end{array}}$ $6936=2^{3}\cdot 3\ \cdot 17^{2}\,$ | ${\begin{array}{r|l}1200&2\\600&2\\300&2\\150&2\\75&3\\25&5\\5&5\\1&\\\end{array}}$ $1200=2^{4}\cdot 3\cdot 5^{2}\,$ |
El M.C.D són els factors comuns amb el menor nombre, és a dir, podem inferir que el seu m.c.d. és:
    $\operatorname {mcd} (6936,1200)=2^{3}\cdot 3=24$
* Si algun dels nombres és enorme, aquest mètode no és operatiu perquè pot ser difícil conèixer-ne els possibles factors. En aquest cas podem fer servir l'algorisme d'Euclides.
* Geomètricament, el màxim comú divisor de a i b és el nombre de punts de coordenades enteres que hi ha en el segment que unix els punts (0, 0) i (a, b), excloent el (0, 0).

## Propietats

Les propietats del m.c.d. són, en certa forma, duals de les del mínim comú múltiple:
* El m.c.d. de diversos nombres és necessàriament més petit o igual que el més petit d'aquests.
* Si un nombre és múltiple d'un altre, el més petit és el m.c.d.
* Si dos nombres són primers entre sí, el seu m.c.d. és 1.
* Els divisors comuns de dos o més nombres són divisors del m.c.d. d'aquests nombres.
* Si dividim dos nombres pel seu m.c.d., els quocients obtinguts són primers entre si.
* El m.c.d. multiplicat pel m.c.m. de dos nombres dona com a resultat el producte dels dos nombres.
    $m.c.d.(a,b)*m.c.m.(a,b)=a*b$
* Qualsevol divisor comú a a i b és un divisor de mcd(a,b).
* m.c.d.(a, b) = m.c.d.(|a|, |b|).
* m.c.d.(a, b) = m.c.d.(b, a).
* m.c.d.(a, 0) = m.c.d.(a, a) = a.
* m.c.d.(a, m.c.d.(b, c)) = m.c.d.(m.c.d.(a, b), c), cosa que permet calcular el m.c.d. de tres o més nombres.
* Si r és el residu de la divisió entera de a entre b, aleshores m.c.d.(a, b) = m.c.d.(b, r). Aquest fet és la base de l'algorisme d'Euclides.
* Si a i b no són tots dos zero, el m.c.d.(a, b) és el nombre més petit que es pot escriure en la forma d = ax + by, amb x i y nombres enters convenients. Aquesta expressió s'anomena Identitat de Bézout i els nombres x i y es poden calcular a partir dels resultats parcials de l'algorisme d'Euclides.

## Usos

El m.c.d. s'empra per a simplificar fraccions, per exemple
    ${\frac {30}{42}}={\frac {2\cdot 3\cdot 5}{2\cdot 3\cdot 7}}={\frac {5}{7}}$
Així, m.c.d.(30, 42) = 6, de manera que es divideix el numerador i el denominador de la fracció inicial per 6 per a obtenir la fracció simplificada.
    ${\frac {30}{42}}={\frac {30/6}{42/6}}={\frac {5}{7}}$

## El m.c.d. als anells principals

Si A és un anell principal i I i J en són ideals, l'ideal I + J és l'ideal màxim comú divisor dels ideals I i J. En el cas de l'anell dels nombres enters, aquesta definició recull la Identitat de Bézout.

## Referències

* 1 2 Corbalán Yuste, F. et al.. Gamma 2 : matemàtiques : Educació Secundària, segon curs. 1a.. Barcelona: Vicens Vives, 2003, p. 10. ISBN 84-316-6978-2.
* ↑ Greatest Common Divisor. MathWorld (anglès)
* 1 2 Corbalán Yuste, 2003, p. 11.
* ↑ «greatest common divisor | mathematics | Britannica» (en anglès). [Consulta: 11 febrer 2022].
* ↑ Corbalán Yuste, 2003, p. 13.

## Vegeu també

* Mínim comú múltiple
* Nombre primer
* Factorització dels enters