Mostrar que
, se, e somente se,
.
Passo 1
Beleza, vamos resumir o que o exercício pede. A gente quer mostrar que
Isso faz parte da teoria de máximo divisor comum (mdc) e de divisibilidade.
O que vamos precisar:
O que vamos precisar:
- Definição de mdc:
significa que é o maior número que divide simultaneamente e . - O fato de que
quer dizer que não existe primo comum que divida e . - O lema de Euclides (no sentido: se um primo divide um produto, divide um dos fatores).
A partir do próximo passo a gente começa a prova de fato.
Passo 2
Prova da direção “
e
”.
- Suponha que
. - Se por absurdo
, então existe um primo que divide , logo e . - Mas aí
implica , e como , teríamos dividindo simultaneamente e . - Isso força
, contradizendo . - Logo não pode existir primo comum entre
e , ou seja . - Exatamente o mesmo raciocínio vale trocando
por , dando .
Passo 3
Prova da direção “
e
”.
- Suponha agora que
e . - Se, por absurdo,
, existe um primo tal que , logo e . - Pelo lema de Euclides, de
segue que ou . - Se
, então seria divisor comum de e , contradizendo . - Se
, dá a mesma contradição com . - Portanto não existe primo dividindo simultaneamente
e , o que implica .
Resposta
Nós provamos as duas direções, logo está demonstrado que