Mostrar que
, onde
(
ou
).
Passo 1
O enunciado pede para mostrar que
, onde
e
ou
.
Informações dadas e o que devemos provar:
Informações dadas e o que devemos provar:
- Temos dois inteiros
e , nem os dois simultaneamente zero. - Definimos
(o máximo divisor comum, tomado aqui como número não negativo). - Devemos provar que o conjunto dos divisores comuns de
e coincide com o conjunto dos divisores de . Ou seja, mostrar igualdade de conjuntos entre
e
A estratégia natural é provar duas inclusões:
e
.
Passo 2
Definições e ferramentas básicas que vamos usar (explicadas com calma):
- Dizemos que um inteiro
divide outro inteiro (escrevemos ) se existe tal que . Ex.: pois . - Uma propriedade simples de divisibilidade: se
e , então para quaisquer inteiros vale . Prova rápida: escreva e ; então , logo é múltiplo de . - Identidade de Bézout (explicação curta): como
e não são ambos zero, existe uma identidade do tipo
para alguns inteiros
. Essa identidade pode ser vista construindo o menor elemento positivo do conjunto
(prova clássica). Esse fato será útil para relacionar divisores comuns de
com divisores de
.
Passo 3
Provar
.
Seja . Então
e
. Pela propriedade que vimos,
divide qualquer combinação linear inteira
. Como
satisfaz a identidade de Bézout, existem inteiros
tais que
Seja
Portanto
. Isso mostra que
. Como
foi um elemento arbitrário de
, concluímos
.
Passo 4
Provar
.
Seja . Então
. Pelo papel de
, sabemos que
é um divisor comum de
e
; isto é,
e
. Agora use a transitividade da divisibilidade: se
e
, então
; se
e
, então
. Logo
divide tanto
quanto
, o que implica
. Como
foi arbitrário em
, segue
.
Seja
Passo 5
Concluir a igualdade dos conjuntos.
Das inclusões dos Passos 3 e 4 temos ambas e
. Portanto os conjuntos são iguais:
Das inclusões dos Passos 3 e 4 temos ambas
Comentário final (pedagogia e calma): a ideia intuitiva é simples — os divisores comuns de
e
são exatamente os divisores do maior divisor comum
. A ferramenta chave foi perceber que qualquer divisor comum divide qualquer combinação linear de
e
, e que o
pode ser escrito como tal combinação (identidade de Bézout).