Sejam
e
e
. Mostre que
.
Passo 1
O enunciado pede para mostrar que, para quaisquer inteiros
e definindo
, temos
. O conteúdo aqui é propriedade do máximo divisor comum (MDC) e vamos precisar usar o fato de que adicionar um múltiplo de um argumento ao outro não altera o MDC.
Passo 2
Começamos lembrando a definição de
: por ser o MDC,
satisfaz duas condições: (i)
divide
e
; (ii) qualquer outro inteiro que divida
e
também divide
.
Mostramos primeiro que divide
e
. De fato, como
divide
e
, temos
divide
e, somando,
divide
. Logo,
é um divisor comum de
e
, o que implica que
.
Mostramos primeiro que
Passo 3
Agora seja
. Pelo mesmo raciocínio,
divide
e
. Mas como
, segue que
também divide
. Portanto,
é divisor comum de
e
, o que dá
.
Como mostramos que e
, concluímos que ambos são iguais.
Como mostramos que
Resposta
(m, n) = (m, n + a m)