Sejam
e
inteiros. Prove que:
(c) Se
, então
.
(c) Se
Passo 1
O enunciado dá que
são inteiros e que
(ou seja,
divide
). Pede para provar que
Informações relevantes que o enunciado fornece:
-
. -
, isto é, existe tal que . - Queremos comparar os divisores comuns a
e com os divisores comuns a e , e concluir que os máximos desses conjuntos (os mdc) são iguais.
Passo 2
Relembrando definições úteis (bem devagarinho):
- Dizemos que
divide e escrevemos quando existe com . - Um divisor comum de dois inteiros
e é um inteiro tal que e . -
é o maior (em valor absoluto) inteiro que é divisor comum de e . Assim, se os conjuntos de divisores comuns de dois pares são iguais, seus mdc também serão iguais. - Propriedade de transitividade da divisibilidade: se
e então . Vou usar isso várias vezes.
Passo 3
Mostro a primeira inclusão de conjuntos (esta é a parte intuitiva): seja
um divisor comum de
e
. Isso significa que
Como
pelo enunciado, pela transitividade temos
. Logo
divide tanto
quanto
, então divide a soma
. Assim
ou seja,
é um divisor comum de
e
. Conclusão: todo divisor comum de
e
é também divisor comum de
e
. Em linguagem de conjuntos:
Passo 4
Agora a inclusão inversa: seja
um divisor comum de
e
. Então
De
e
(hipótese) segue, pela transitividade, que
. Portanto
divide
e divide
, então divide a diferença
, que é exatamente
. Assim
isto é,
é divisor comum de
e
. Portanto
Passo 5
Das inclusões dos Passos 3 e 4 segue que os dois conjuntos de divisores comuns coincidem:
Se dois pares têm exatamente o mesmo conjunto de divisores comuns, o maior divisor comum (o
) também é o mesmo para os dois pares. Portanto
Passo 6
Observação e generalização útil para prova de prova: o argumento acima não usa nada específico de
além de ser múltiplo de
. Se
com
, então a mesma demonstração mostra que, para todo inteiro
,
Isso é uma propriedade prática na prova: somar um múltiplo de um dos números ao outro não altera o mdc. Um exemplo concreto para fixar: tome
,
,
(aqui
). Temos
e
, conforme a propriedade.