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}$ (3^o resto) pois $r_{4} = 0$, ou seja, $mdc (3125, 495) = 45$.