Mostre que se
então
.
Passo 1
O enunciado quer que a gente mostre que, dados inteiros
,
e
, se
então
Vamos usar a definição de congruência (divisibilidade) e a definição de máximo divisor comum como maior elemento do conjunto dos divisores positivos comuns.
Passo 2
Da congruência
segue que
ou seja, existe um inteiro
tal que
Agora, seja
um divisor comum de
e
. Então
Como
e
, concluímos que
. Mas então,
Portanto, todo divisor comum de
e
também divide
, ou seja, é divisor comum de
e
.
Passo 3
O argumento anterior vale de forma simétrica trocando
por
. Logo, todo divisor comum de
e
também divide
. Concluímos que os conjuntos de divisores comuns de
e de
são exatamente os mesmos. Como o máximo divisor comum é o maior número inteiro positivo nesse conjunto, segue que