Màxim comú divisor

De Viquipèdia
Dreceres ràpides: navegació, cerca

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.

Generalitats[modifica | modifica el codi]

Interpretació geomètrica del màxim comú divisor de 10 i 25, mcd(10,25)=5.
  • 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 prendre els factors comuns amb el seu menor exponent. Multiplicant aquests factors comuns trobem el màxim comú divisor.

Exemple: per calcular el màxim comú divisor de 48 i de 60 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 MCD són els factors comuns amb el menor exponent, é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 molt gran, 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[modifica | modifica el codi]

Les propietats del m.c.d. són, en certa forma, duals de les del mínim comú múltiple:

  • 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.
  • El màxim comú divisor de dos nombres i el mínim comú múltiple estan lligats per la relació: m.c.d.(a, b)·m.c.m.(a, b) = |ab|.

Usos[modifica | modifica el codi]

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[modifica | modifica el codi]

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.

Vegeu també[modifica | modifica el codi]