MDC - Máximo Divisor Comum

Sabemos que o divisor de um número inteiro é aquele que divide o número, isto é, a divisão entre o dividendo e o divisor propriamente dito é exata.

Por exemplo, 6 é divisor de 12, pois a divisão de 12 por 6 resulta em quociente igual a 2 e resto 0.

Mas é evidente que um número pode ter mais de um divisor. Além do 6, os números 1, 2, 3, 4 e o próprio 12 são divisores de 12.

O conjunto dos divisores de um número é sempre finito. Se denotarmos por \(D(12)\) o conjunto dos divisores de 12, temos que:

$$D(12)=\{1,2,3,4,6,12\}$$

E do mesmo modo, podemos enumerar os divisores de 18:

$$D(18)=\{1,2,3,6,9,18\}$$

Observe que os números 1, 2, 3 e 6 são divisores comuns ao 12 e ao 18, sendo, claramente, o número 6 o maior entre eles.

O nosso objetivo é: dados dois ou mais números, queremos determinar o máximo divisor comum (MDC) entre eles.

Uma das maneiras é, de fato, fazer o que acabara de ser demonstrado: tomar todos os divisores de cada número e encontrar o maior. Porém, tal processo pode se tornar longo e pouco eficiente.

Abaixo, exemplificamos um método que faz o uso da decomposição em fatores primos.

Vamos calcular o MDC entre os números 24 e 32. Para isso, nós os escrevemos à esquerda de uma reta vertical, conforme abaixo:

$$\begin{array}{cc|c} 24, & 32 & \\ & & \\ & & \\ & & \end{array}$$

À direita da reta, escreveremos os fatores primos que dividem os números à esquerda ao mesmo tempo. Neste caso, 2 divide 24 e 32, logo:

$$\begin{array}{cc|c} 24, & 32 & 2 \\ & & \\ & & \\ & & \end{array}$$

E, na próxima linha à esquerda, colocamos o resultado da divisão de 24 por 2 e de 32 por 2:

$$\begin{array}{cc|c} 24, & 32 & 2 \\ 12, & 16 & \\ & & \\ & & \end{array}$$

O próximo passo consiste no anterior: colocar à direita da reta o fator primo que divide agora 12 e 16 ao mesmo tempo; se existir, fazer a divisão na próxima linha:

$$\begin{array}{cc|c} 24, & 32 & 2 \\ 12, & 16 & 2 \\ 6, & 8 & \\ & & \end{array}$$

E, mais uma vez, 2 divide os dois número à esquerda ao mesmo tempo:    

$$\begin{array}{cc|c} 24, & 32 & 2 \\ 12, & 16 & 2 \\ 6, & 8 & 2 \\ 3, & 4 & \end{array}$$

Como não existe nenhum número primo que divida 3 e 4, então o processo é encerrado. O MDC será o produto dos fatores primos à direita:

$$\mdc(24,32)=2\cdot2\cdot2=8$$

Diremos que dois (ou mais) números são primos entre si caso o MDC deles seja igual a 1.

Por exemplo, os números 15 e 8 são primos entre si, pois:

$$\mdc(15,8)=1$$

De fato, a partir do processo exemplificado anteriormente, temos que não existe nenhum número primo que divide 15 e 8 ao mesmo tempo:

$$\begin{array}{cc|c} 15, & 8 & \\ & & \\ & & \end{array}$$

Logo, $$\mdc(15,8)=1$$ pois 1 é o divisor de todos os números.

Se \(a\) for divisor de \(b\), então:

$$\mdc(a,b)=a$$

Por exemplo, o MDC entre os números 20 e 40 é igual a 20, pois 20 é divisor de 40. Se tomarmos os números 5, 10 e 30, temos que 5 é divisor de 10 e de 30, logo:

$$\mdc(5,10,30)=5$$