Sejam a, b inteiros positivos distintos de 1 , com decomposição em produto de potências de primos
\begin{aligned} a & =p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}} \\ b & =p_{1}^{b_{1}} p_{2}^{b_{2}} \cdots p_{k}^{b_{k}} \end{aligned}
em que a_{i} \geq 0, b_{i} \geq 0 para cada i=1,2, \ldots, k. Prove que
\operatorname{mdc}(a, b)=p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}\\, onde \(m_{j}=\min \left\{a_{j}, b_{j}\right\} para cada j=1,2, \ldots, k;(complete a prova das notas de aula))

Passo 1

O enunciado fornece dois inteiros positivos a e b (ambos distintos de 1) e suas decomposições em potências de primos sobre os mesmos primos p_{1},p_{2},\ldots,p_{k}:
a = p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}, \qquad b = p_{1}^{b_{1}} p_{2}^{b_{2}} \cdots p_{k}^{b_{k}},
onde, para todo i=1,2,\ldots,k, temos a_{i}\ge 0 e b_{i}\ge 0.
A tarefa é provar que
\operatorname{mdc}(a,b)=p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}},
onde, para cada j=1,2,\ldots,k, definimos m_{j}=\min\{a_{j},b_{j}\}.
Informações relevantes listadas:
  • As escritas de a e b são fatorações em primos (podemos entender que primes não listados têm expoente zero).
  • Queremos provar que o máximo divisor comum (mdc) é o produto dos mesmos primos elevados ao menor expoente entre a e b.

Passo 2

Lembrete do que significa “máximo divisor comum”: um inteiro d é \operatorname{mdc}(a,b) quando (i) d divide a e d divide b, e (ii) se c é qualquer inteiro que divide simultaneamente a e b, então c divide d. Ou seja, o \operatorname{mdc} é um divisor comum que é múltiplo de todos os outros divisores comuns — é o maior em relação à divisibilidade. Vou construir um candidato natural para o mdc e depois mostrar que ele satisfaz essas duas propriedades.

Passo 3

Definimos o candidato
d \coloneqq p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}, \qquad\text{onde } m_{j}=\min\{a_{j},b_{j}\}.
Primeiro vou mostrar que d divide a e d divide b.
Explicação de um fato usado: se temos uma potência de primo \;p^{r} e \;p^{s} com r,s\ge0, então \;p^{r} divide \;p^{s} exatamente quando r\le s. Isto é porque a multiplicação por p aumenta o expoente; dividir significa ter expoente menor ou igual. Esse é um fato elementar sobre potências de um mesmo primo.
Agora, como m_{j}=\min\{a_{j},b_{j}\}, temos m_{j}\le a_{j} para todo j. Assim para cada j,
p_{j}^{m_{j}} \text{ divide } p_{j}^{a_{j}}.
Multiplicando sobre todos os j=1,\dots,k, obtemos que
p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}
divide
p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}} = a.
Portanto d divide a. Análogo, como m_{j}\le b_{j} para todo j, segue que d divide b. Concluímos que d é um divisor comum de a e b.

Passo 4

Agora mostro que d é “máximo” no sentido da divisibilidade: qualquer divisor comum c de a e b divide d.
Pela fatoração única em primos (teorema fundamental da aritmética), qualquer inteiro positivo c pode ser escrito (sobre os mesmos primos p_{1},\dots,p_{k}, atribuindo expoente zero quando o primo não aparece) como
c = p_{1}^{c_{1}} p_{2}^{c_{2}} \cdots p_{k}^{c_{k}},
com c_{j}\ge0 inteiros. Se c divide a, então para todo j vale c_{j}\le a_{j} (novamente pelo fato sobre divisibilidade de potências de um mesmo primo). Se c também divide b, então c_{j}\le b_{j} para todo j. Portanto, para cada j temos
c_{j} \le \min\{a_{j},b_{j}\} = m_{j}.
Isto implica que, para todo j, p_{j}^{c_{j}} divide p_{j}^{m_{j}}. Multiplicando, obtemos c divide d. Assim qualquer divisor comum c de a e b divide d.
Essa propriedade (todo divisor comum divide d) é exatamente a segunda condição necessária para que d seja o \operatorname{mdc}(a,b). Juntando com a primeira condição (já provada no Passo 3), concluímos que d é o máximo divisor comum.

Passo 5

Resumo didático e exemplo pequeno para fixar a intuição: o mdc pega, para cada primo, o expoente que aparece tanto em a quanto em b, ou seja, o menor dos expoentes. Exemplo concreto: se
a=60=2^{2}\,3^{1}\,5^{1},\qquad b=90=2^{1}\,3^{2}\,5^{1},
então os expoentes mínimos são m_{2}=1 para 2, m_{3}=1 para 3 e m_{5}=1 para 5, logo
\operatorname{mdc}(60,90)=2^{1}\,3^{1}\,5^{1}=30.
Esse exemplo ilustra o argumento geral: para cada primo tomamos o menor expoente presente nas duas fatorações.

Resposta

\operatorname{mdc}(a,b)=p_{1}^{m_{1}} p_{2}^{m_{2}} \cdots p_{k}^{m_{k}}, onde m_{j}=\min\{a_{j},b_{j}\} para cada j=1,2,\ldots,k.

Exercícios relacionados