Máximo divisor comum

Referência : Tavares, J., Geraldo, A., (2021) Máximo divisor comum, Rev. Ciência Elem., V9(1):009
Autor: João Nuno Tavares e Ângela Geraldo
Editor: José Ferreira Gomes
DOI: [https://doi.org/10.24927/rce2021.009]

---

Definição

O máximo divisor comum entre dois ou mais números inteiros (um deles necessariamente diferente de zero) é o maior número inteiro positivo que é divisor (divisão com resto zero) desses números. Por exemplo, o maior divisor que é comum a \(9\) e a \(6\) é \(3\), portanto, o máximo divisor comum entre \(9\) e \(6\) é o número inteiro \(3\).

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

3) Se \(\mbox{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 \(\mbox{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 \(\mbox{mdc}(9,6)=3\).

Algumas propriedades

• Se \(d\) é um número inteiro tal que \(d \neq 0\), temos que \(\mbox{mdc}(da, db)=d\,\, \mbox{mdc}(a,b)\);
• Se \(d \in \mathbb{Z}\backslash \{0\}\), temos que \(\displaystyle \mbox{mdc}\left(\frac{a}{d},\frac{b}{d}\right)=\frac{\mbox{mdc}(a,b)}{d}\);
• Comutatividade: \(\mbox{mdc}(a,b)=\mbox{mdc}(b,a)\);
• Associatividade: \(\mbox{mdc}(\mbox{mdc}(a,b),c)=\mbox{mdc}(a,\mbox{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, \(\mbox{mdc}(a,b) \times \mbox{mmc}(a,b)=ab\).

Cálculo do \(mdc\)

Em seguida mostraremos três processos que nos permitem determinar o \(\mbox{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.

\(1º\) - 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 \(\mbox{mdc}(32,24)\)?

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

\(\mathcal{D}_{32}=\{1,2,4,{\bf 8},16\}\)

\(\mathcal{D}_{24}=\{1,2,3,4,6,{\bf 8},12\}\)

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

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

\(2º\) - 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 \(\mbox{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 \(\mbox{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 \times 2 \times 5=2^2 \times 5\)

\(64=2 \times 2 \times 2 \times 2 \times 2 \times 2=2^6\)

Logo, o \(\mbox{mdc}(52,20,64)=2 \times 2=4\).

\(3º\) - Algoritmo de Euclides

O Algoritmo de Euclides permite determinar o \(\mbox{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 \(\mbox{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 \(\mbox{mdc}(3125,495)\)?

\(\displaystyle \frac{3125}{495}=6\) com resto \(r_1=180\);

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

\(\displaystyle \frac{180}{135}=1\) com resto \(r_3=45\);

\(\displaystyle \frac{135}{45}=3\) com resto \(r_4=0\);

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

Código do algoritmo de Euclides para cálculo do \(\mbox{mdc}\)

Pseudocódigo Dados dois números inteiros positivos \(m\) e \(n\). Consideremos \(m>n\). 1 - Efetua-se a divisão de \(m\) por \(n\), considerando \(r\) o resto dessa divisão; 2 - Se \(r=0\), o divisor, \(n\), é o \(\mbox{mdc} (m,n)\); 3 - Se \(r \neq 0\), voltar ao passo 1. 4 - O \(\mbox{mdc} (m,n)\) é assim o divisor da divisão que tem resto igual a zero.

Código em \(\mathcal{PYTHON}\)

---

Criada em 16 de Julho de 2013
Revista em 20 de Janeiro de 2021
Aceite pelo editor em 15 de Março de 2021