Sejam
inteiros positivos distintos de 1 , com decomposição em produto de potências de primos
em que
para cada
. Prove que
para cada
;(complete a prova das notas de aula))
para cada
Passo 1
O enunciado fornece dois inteiros positivos
e
(ambos distintos de
) e suas decomposições em potências de primos sobre os mesmos primos
:
onde, para todo
, temos
e
.
A tarefa é provar que
A tarefa é provar que
onde, para cada
, definimos
.
Informações relevantes listadas:
Informações relevantes listadas:
- As escritas de
e 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
e .
Passo 2
Lembrete do que significa “máximo divisor comum”: um inteiro
é
quando (i)
divide
e
divide
, e (ii) se
é qualquer inteiro que divide simultaneamente
e
, então
divide
. Ou seja, o
é 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
Primeiro vou mostrar que
divide
e
divide
.
Explicação de um fato usado: se temos uma potência de primo
e
com
, então
divide
exatamente quando
. Isto é porque a multiplicação por
aumenta o expoente; dividir significa ter expoente menor ou igual. Esse é um fato elementar sobre potências de um mesmo primo.
Agora, como
, temos
para todo
. Assim para cada
,
Multiplicando sobre todos os
, obtemos que
divide
Portanto
divide
. Análogo, como
para todo
, segue que
divide
. Concluímos que
é um divisor comum de
e
.
Passo 4
Agora mostro que
é “máximo” no sentido da divisibilidade: qualquer divisor comum
de
e
divide
.
Pela fatoração única em primos (teorema fundamental da aritmética), qualquer inteiro positivo
pode ser escrito (sobre os mesmos primos
, atribuindo expoente zero quando o primo não aparece) como
com
inteiros. Se
divide
, então para todo
vale
(novamente pelo fato sobre divisibilidade de potências de um mesmo primo). Se
também divide
, então
para todo
. Portanto, para cada
temos
Isto implica que, para todo
,
divide
. Multiplicando, obtemos
divide
. Assim qualquer divisor comum
de
e
divide
.
Essa propriedade (todo divisor comum divide
) é exatamente a segunda condição necessária para que
seja o
. Juntando com a primeira condição (já provada no Passo 3), concluímos que
é 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
quanto em
, ou seja, o menor dos expoentes. Exemplo concreto: se
então os expoentes mínimos são
para
,
para
e
para
, logo
Esse exemplo ilustra o argumento geral: para cada primo tomamos o menor expoente presente nas duas fatorações.