Sejam
tais que
. Mostre que:
Passo 1
O enunciado diz que
e que
. A tarefa é mostrar que
. Ou seja, preciso provar que nenhum inteiro
divide simultaneamente
e
.
A estratégia que vou usar é mostrar que nenhum primo
pode dividir simultaneamente
e
. Se nenhum primo divide ambos, então nenhum inteiro
(que tem um primo como divisor) pode dividir ambos, e portanto o máximo divisor comum é
. Para isso vou usar o lema de Euclides: se
é primo e
então
ou
.
Passo 2
Lema de Euclides: se
é primo e
então
ou
.
Justificativa: suponha que
e que
. Como
é primo e não divide
, temos
. Pelo Teorema de Bézout existe uma combinação linear inteira
para alguns inteiros
. Multiplicando ambos os lados por
obtemos
Pelo hipótese
o termo
é múltiplo de
, e obviamente
também é múltiplo de
. Portanto a soma
é múltiplo de
, o que implica
. Assim, se
então necessariamente
. Isso prova o lema.
Passo 3
Agora aplico o lema ao problema. Suponha, por absurdo, que existe um primo
tal que
e
. Como
, pelo lema de Euclides segue que
ou
. Vou tratar as duas possibilidades:
Caso
. Como também
, ao subtrair
das duas quantidades temos que
divide a diferença:
Logo
divide tanto
quanto
, ou seja,
é um divisor comum de
e
. Isso contradiz a hipótese
.
Caso
. Argumento análogo: como
e
, subtraindo
obtemos
. Novamente
divide
e
, contradizendo
.
Passo 4
Concluímos que não existe primo
que divida simultaneamente
e
. Logo não existe inteiro
que divida ambos (pois todo
tem um primo como divisor). Portanto o máximo divisor comum é
, isto é,
.