Máximo divisor comum e mínimo múltiplo comum

O máximo divisor comum e o mínimo múltiplo comum

Na aula sobre divisibilidade e divisão com resto estudou-se a relação $d \mid a$ entre dois naturais. Quando se consideram dois números ao mesmo tempo, interessam os divisores que eles têm em comum e os múltiplos que compartilham. Todo par de naturais $a$ e $b$ tem pelo menos um divisor comum, o $1$, e no máximo um número finito deles, porque nenhum divisor de $a$ supera $a$; tem, além disso, infinitos múltiplos comuns, entre eles o produto $ab$. Se é assim, faz sentido a definição seguinte.

Definição (máximo divisor comum e mínimo múltiplo comum). O máximo divisor comum de dois naturais $a$ e $b$, que se escreve $\operatorname{mdc}(a, b)$, é o maior natural que divide ambos. O mínimo múltiplo comum, que se escreve $\operatorname{mmc}(a, b)$, é o menor natural que é múltiplo de ambos.

O segundo é o menor elemento de um conjunto não vazio de naturais, que existe pelo princípio da boa ordenação. O primeiro é o maior elemento do conjunto dos divisores comuns, que não é vazio e é limitado por $a$; que um conjunto não vazio de naturais limitado superiormente tem máximo segue-se também da boa ordenação: o conjunto de suas cotas superiores não é vazio e tem um mínimo $M$, e $M$ pertence ao conjunto, porque, se não pertencesse, todo elemento seria menor que $M$ e, como não há naturais entre $M - 1$ e $M$, não maior que $M - 1$, que seria uma cota superior menor que $M$ (se $M = 1$, o conjunto é $\{1\}$ e contém $M$). Por exemplo, os divisores comuns de $12$ e $18$ são $1$, $2$, $3$ e $6$, e seus múltiplos comuns são $36$, $72$, $108$, e assim por diante:

Da definição seguem-se de imediato alguns casos particulares: $\operatorname{mdc}(a, 1) = 1$ e $\operatorname{mmc}(a, 1) = a$; $\operatorname{mdc}(a, a) = \operatorname{mmc}(a, a) = a$; e, se $a$ divide $b$, então $\operatorname{mdc}(a, b) = a$ e $\operatorname{mmc}(a, b) = b$. Ambas as operações são, além disso, simétricas: a ordem dos números não altera o resultado.

Cálculo por meio da decomposição em fatores primos

Pelo teorema fundamental da aritmética, todo natural maior que $1$ se decompõe de maneira única em fatores primos. Convém escrever $a$ e $b$ com os mesmos primos $p_1, \ldots, p_k$, admitindo expoentes nulos para os primos que só aparecem em um deles:

Um natural $d$ divide $a$ exatamente quando em sua decomposição não aparecem outros primos além dos de $a$, e cada um com expoente não maior que o que tem em $a$. Segue-se daí que $d$ divide ao mesmo tempo $a$ e $b$ quando o expoente de cada primo em $d$ não supera nenhum dos dois expoentes; o maior divisor comum obtém-se, portanto, tomando para cada primo o menor dos dois expoentes. Do mesmo modo, $m$ é múltiplo comum quando o expoente de cada primo em $m$ alcança os dois, e o menor múltiplo comum toma para cada primo o maior dos dois expoentes. Por exemplo:

O método é claro, mas depende de saber fatorar, e fatorar números grandes é muito custoso: não se conhece nenhum procedimento rápido para fazê-lo. O algoritmo da seção seguinte calcula o máximo divisor comum sem fatorar, só com divisões.