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]

[editar] 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;

[editar] 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$.

[editar] 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$.

[editar] 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$.

[editar] 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}$