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.^[1]^[2] 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.^[3]^[4]

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.^[1]

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.^[3]

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.^[5]

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,0 ^1,1 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)
↑ ^3,0 ^3,1 Corbalán Yuste, 2003, p. 11.
↑ «greatest common divisor | mathematics | Britannica» (en anglès). [Consulta: 11 febrer 2022].
↑ Corbalán Yuste, 2003, p. 13.