Se
divide
e
, então
Passo 1
O enunciado dá que
e que
divide
e
. O que é pedido é provar a igualdade
Informações relevantes extraídas do enunciado:
-
divide e , portanto e são inteiros. - A função
significa o máximo divisor comum de e .
A partir daqui vamos provar a identidade mostrando que os divisores comuns dee estão em correspondência com os divisores comuns de e .
Passo 2
Defina
que são inteiros por hipótese. Seja
Como
divide
e
,
é um divisor comum de
e
. Pelo caráter “máximo” do
, qualquer divisor comum de
e
divide
; em particular
divide
. Logo existe um inteiro
tal que
Passo 3
Vou mostrar que
é um divisor comum de
e
. Como
divide
e
, existem inteiros
e
tais que
Dividindo essas igualdades por
(lembrando que
e
) obtemos
Portanto
divide
e
; ou seja,
é um divisor comum de
e
.
Passo 4
Agora mostro que
é o maior divisor comum de
e
. Seja
um divisor comum arbitrário de
e
. Então existem inteiros
e
tais que
Multiplicando por
obtemos
ou seja,
divide
e
. Como
é o máximo divisor comum de
e
, segue que
divide
. Mas
, então
divide
. Como
, podemos cancelar
da divisibilidade e obter
divide
. Portanto qualquer divisor comum
de
e
divide
.
Passo 5
Das etapas anteriores concluímos que
é um divisor comum de
e
e que qualquer outro divisor comum de
e
divide
. Essa é exatamente a propriedade que caracteriza o máximo divisor comum. Logo
Passo 6
Voltando às definições
e
e usando
com
, obtemos
Isto prova a igualdade desejada.