Divisibilidade

Estruturas Matemáticas para Computação
Mínimo Múltiplo Comum, Mudança de Base e
Critérios de Divisibilidade - Apostila 04
Vinicius Rispoli
Módulo 1

1

Mínimo Múltiplo Comum

O Mínimo Múltiplo Comum de dois números positivos a e b é o menor inteiro positivo que é divisível por a e b. Iremos denotá-lo por [a, b].
Exemplo:
Para determinarmos o mínimo múltiplo comum entre os números 54 e 36 podemos para cada um dos números encontrar o seu conjunto de seus múltiplos e então verificarmos qual é o menor elemento em comum nos conjuntos. Assim, o conjunto de divisores de 36 é
M36 = {36, 72, 108, 144, 180, · · ·} e os de 54 é
M54 = {54, 108, 162, 216, 270, · · ·}.
Vemos que em ambos os conjuntos de divisores o menor elemento em comum é o número 108, portanto
[54, 36] = 108. Assim como encontrar o mdc através de um elemento comum no conjunto de divisores não era prático, essa também não é uma forma nem um pouco prática de se cálcular o mmc entre dois números. Se os números forem suficientemente grandes o seu conjunto de divisores pode ter muitos elementos o que inviabiliza o uso dessa forma de calcular. Logo, precisamos de uma forma mais eficiente, o que será discutido no teorema a seguir.

Teorema 1: β1 β2 αn βn
2
Se a = p1α1 pα
2 · · · pn e b = p1 p2 · · · pn , em que pi são números primos distintos, então max(α1 ,β1 ) max(α2 ,β2 ) p2 [a, b] = p1

n ,βn )
· · · pmax(α
.
n

Demonstração: Da definição do mínimo múltiplo comum nenhum fator promo pi deste mínimo poderá ter um expoente que seja inferior nem a αi e nem a βi . Se tormarmos, pois, o maior destes dois para expoente de pi teremos, não apenas um múltiplo comum, mas o menor possível entre todos eles. O que conclui a demonstração.

Exemplo:
• Para determinar o mínimo múltiplo comum entre 96 e 144 devemos primeiramente encontrarmos a decomposição em fatores primos destes números. Temos que, 96 = 25 · 3 e 144 = 24 · 32 e portanto
[96, 144] = 2max(5,4) · 3max(1,2) = 288.