Sejam
e
inteiros, com
ou
. Prove que
.
Passo 1
O enunciado dá que
e
são inteiros e que
ou
(ou ambos). O que se pede é provar que
Ou seja, mostrar que o máximo divisor comum de
e
divide o inteiro
.
Passo 2
Vou lembrar e explicar de forma bem direta algumas noções que vou usar.
Definição de divisibilidade. Dizemos que um inteiro
divide um inteiro
e escrevemos
se existe um inteiro
tal que
. Exemplo rápido:
porque
.
Propriedade útil (linearidade da divisibilidade). Se
e
então, para quaisquer inteiros
, vale
. A demonstração é simples: escrevendo
e
com
, obtemos
que é múltiplo de
. Uma instância importante dessa propriedade é que, se
e
, então
(tome
e
).
Passo 3
Defina
. Pela definição de máximo divisor comum,
é um inteiro que divide ambos
e
; isto é,
Aplicando a propriedade do passo anterior com
e
, temos que
divide a diferença
Formalmente, como
e
, segue
.
Passo 4
Comentário adicional (opcional, para fixar a ideia). A observação feita equivale ao passo do algoritmo de Euclides que diz que
. Portanto o máximo divisor comum de
e
é também divisor de
. O argumento apresentado é curto e direto: funciona para todos os inteiros
(com a ressalva do enunciado que não são ambos zero). Note também que o sinal (positivo/negativo) não altera a divisibilidade, então costuma-se considerar
não negativo.