Formalmente, o inteiro positivo \(d\) é o máximo divisor comum dos inteiros \(a\) e \(b\), não simultaneamente nulos, se as condiçoes seguintes forem satisfeitas:

  1. \(d|a\) e \(d|b\);
  2. \(\forall x\in \mathbb{Z}\),\(x|a\) e \(x|b\) então \(x|d\)


Se \(mdc (a, b) = 1\), ou seja, os números inteiros \(a\) e \(b\) não têm nenhum outro divisor comum para além de 1, dizemos que \(a\) e \(b\) são primos entre si;

Notação

Utilizamos a notação \(mdc (a, b)\) ou simplesmente \((a, b)\) para designar o máximo divisor comum entre os números inteiros \(a\) e \(b\). Retomando o exemplo anterior, escreveríamos que \(mdc (9,6) = 3\).


Algumas propriedades

  • Se \(d\) é um número inteiro tal que \(d\neq 0\), temos que \(mdc (da, db) = d \times mdc (a, b)\);
  • Se \(d\in \mathbb{Z}\setminus \left \{ 0 \right \}\), temos que \(\left ( \frac{a}{d},\frac{b}{d} \right )=\frac{mdc\left ( a,b \right )}{d}\),
  • Comutatividade: \(mdc (a, b) = mdc (b, a)\);
  • Associatividade: \(mdc (mdc (a, b) , c) = mdc (a,mdc (b, c))\);
  • O produto do máximo divisor comum de \(a\) e \(b\) pelo mínimo múltiplo comum desses mesmos números, é igual ao produto entre \(a\) e \(b\), ou seja, \(mdc\left ( a,b \right )\times mmc\left ( a,b \right )=ab\).


Cálculo do máximo divisor comum

Em seguida mostraremos três processos que nos permitem determinar o \(mdc\) de dois ou mais números inteiros. A diferença entre os três algoritmos reside essencialmente na morosidade de cada um deles consoante os números em causa.


Lista dos divisores

Neste processo o que se pretende, inicialmente, é que se escreva a lista ordenada dos divisores de cada um dos números. Em seguida, encontra-se o maior número que aparece em todas as listas ordenadas ou seja, o maior divisor comum a todos os números considerados.


Exemplo

Como determinar o \(mdc (32, 24)\)?

Comecemos por criar as listas ordenadas dos divisores de cada um dos números:

\(D_{32}=\left \{ 1,2,4,\mathbf{8},16 \right \}\)

\(D_{24}=\left \{ 1,2,3,4,6,\mathbf{8},12 \right \}\)


Pretendemos encontrar o maior elemento do conjunto \(D_{32}\cap D_{24}\).

Portanto, o \(mdc (32, 24) = 8\).


Fatorização em números primos

Podemos igualmente utilizar a fatorização em números primos de cada um dos números para determinar o \(mdc\). Para isso, basta escrevermos cada um dos números em questão como produto de números primos. O máximo divisor comum desses números é igual ao produto dos fatores primos comuns, cada um elevado ao menor dos expoentes. Vejamos o seguinte exemplo.


Exemplo

Como calcular o \(mdc (52, 20, 64)\) através da fatorização em números primos?

\(52=2\times 2\times 13=2^{2}\times 13\).

\(20=2\times2\times5=2^{2}\times 5\)

\(64=2\times 2\times 2\times 2\times 2\times 2\times 2=2^{6}\).

Logo, o \(mdc\left ( 52,20,64 \right )=2\times 2=4\).


Algoritmo de Euclides

O Algoritmo de Euclides permite determinar o \(mdc (a, b)\), com \(a\) e \(b\) dois inteiros positivos, realizando sucessivas divisões de forma a encontrar uma sequência estritamente decrescente de inteiros não negativos (restos das divisões). Encontrada a sequência, o \(mdc (a, b)\) é igual ao resto que antecede o resto nulo, ou seja, ao número da sequência que antecede o zero. Vejamos a aplicação deste algoritmo num exemplo concreto.


Exemplo

Como determinar o \(mdc (3125, 495)\)?

\(\frac{3125}{495}=6\) com resto \(r_{1}=180\);

\(\frac{495}{180}=2\) com resto \(r_{2}=135\);

\(\frac{180}{135}=1\) com resto \(r_{3}=45\);

\(\frac{135}{45}=3\) com resto \(r_{4}=0\);

Concluímos então que o \(mdc (3125, 495)\) é igual ao \(r_{3}\) (3o resto) pois \(r_{4} = 0\), ou seja, \(mdc (3125, 495) = 45\).