Mostre que, se
, então
.
Passo 1
O enunciado dá que
e que
onde
é o máximo divisor comum de
e
. A pergunta é: provar que
Observação necessária: se
então
e a igualdade fica
, caso em que a conclusão pode falhar (por exemplo, quaisquer
servem). Portanto, para que a afirmação faça sentido e seja verdadeira, vamos assumir que
, isto é, que
e
não são ambos zero.
Passo 2
Defina
. Por definição de máximo divisor comum,
é um inteiro positivo que divide tanto
quanto
. Logo existem inteiros
e
tais que
Aqui expliquei por que esses
e
existem: se um inteiro
divide
, então
é um inteiro; chamei esse inteiro de
(mesmo para
).
Passo 3
Substituindo
e
na hipótese
obtemos
Agrupando,
Como assumimos
, podemos dividir ambos os lados por
(divisão por zero não é permitida, por isso a observação no Passo 1). Dessa divisão resulta
Isto é, existe uma combinação inteira de
e
que vale
.
Passo 4
Mostramos agora que
. Seja
o máximo divisor comum de
e
. Pelo significado de máximo divisor comum,
divide
e
divide
. Logo
divide qualquer combinação inteira de
e
; em particular,
divide
Mas do Passo 3 sabemos que
. Logo
divide
. Os únicos divisores inteiros de
são
e
, e o máximo divisor comum é tomado como não negativo, logo
. Portanto
.
Passo 5
Resumo da lógica: escrever
e
como múltiplos de
, substituir na igualdade dada, dividir por
para obter uma combinação inteira
, e então usar que qualquer divisor comum de
e
divide essa combinação, forçando-o a ser
.