Màxim comú divisor

De Viquipèdia

El màxim comú divisor (m.c.d.; mcd) de dos o més nombres naturals és el major divisor possible de tots ells.

Tot i que podem anar provant nombres naturals un per un fins trobar el m.c.d., existeix un mètode general per trobar-lo. Consisteix en descomposar tots els nombres en factors primers i prendre els factors comuns amb el seu menor exponent. Multiplicant aquests factors comuns trobem el màxim comú divisor.

Per exemple, de les factoritzacions de 6936 i 1200,

6936 = 23 · 3 · 172  
1200 = 24 · 3 · 52

podem inferir que el seu m.c.d. és 23 · 3 = 24

Si el nombre és molt gran aquest mètode no és operatiu perquè no coneixem els possibles factors. En eixe cas hem d'utilitzar el algoritme d'Euclides.

[edita] 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}

Ací, m.c.d.(30, 42) = 6, així 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}


[edita] Propietats

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).

El m.c.d. de tres nombres es pot calcular com segueix: mcd(a,b,c) = mcd(a, mcd(b,c)).

[edita] Vegeu també