Máximo divisor comum
📧 , 📧
- * CMUP/ Universidade do Porto
- ɫ CMUP/ Universidade do Porto
Referência Tavares, J., Geraldo, A., (2021) Máximo divisor comum, Rev. Ciência Elem., V9(1):009
DOI http://doi.org/10.24927/rce2021.009
Palavras-chave números primos, factorização, divisores, Algoritmo de Euclides
Resumo
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:
- \(d|a\) e \(d|b\);
- \(\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\).
Este artigo já foi visualizado 3673 vezes.