Demonstrar que o mdc
se e somente se o mdc (
) = 1 .
Passo 1
O enunciado pede para mostrar que
O conteúdo aqui é a propriedade de que qualquer divisor comum a dois números também divide qualquer combinação linear deles. Vamos usar que, se
e
, então
.
Passo 2
Mostramos primeiro que todo divisor comum a
e
também é divisor comum a
e
. Seja
tal que
Então, pela propriedade de combinações lineares,
logo todo divisor comum de
é divisor comum de
. Assim
Passo 3
Agora o recíproco: todo divisor comum a
e
também divide
. Seja
tal que
Então, como
, temos
Portanto todo divisor comum de
é divisor comum de
, e vale
Passo 4
Das desigualdades
concluímos que
Em particular,
se, e somente se,
.
Resposta
Como mostramos que
, segue imediatamente que