El màxim comú divisor (mcd) de dos o més nombres enters és, a excepció del signe, el major divisor possible de tots.Greatest Common Divisor. MathWorld 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 miniatura|Interpretació geomètrica del màxim comú divisor de 10 i 25, .Si bé podem anar provant nombres naturals un per un fins a trobar el m.c.d., hi ha un mètode general per a 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 a calcular el màxim comú divisor de 6936 i de 1200, factoritzem en factors primers:
|+
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:
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 uneix 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 si, 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.
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
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.
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 lideal 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
Vegeu també
Mínim comú múltiple Nombre primer Factorització dels enters
Categoria:Teoria de nombres