Mostre que se
e
então
.
Passo 1
Temos como dados \
e \
. O conteúdo aqui é teoria de divisibilidade e propriedades do máximo divisor comum (gcd).
Passo 2
Como
, pela definição de gcd vem que
e
.
Passo 3
Pela propriedade de divisibilidade, se um número divide dois números então divide qualquer combinação linear deles. Assim, de
e
segue que
e
.
Passo 4
Agora,
é divisor comum de
e
. Por definição do gcd, todo divisor comum de dois números divide o gcd desses números. Logo,
.