Sejam
inteiros tais que
. Mostre que se
então $a \mid d c.
Passo 1
O enunciado dá e pede o seguinte (vou listar claramente o que sabemos e o que precisamos mostrar):
- Sabemos que
são inteiros. - Sabemos que
. Ou seja, há um inteiro (vou chamar de ) tal que . - Sabemos que
. Isto é, o máximo divisor comum de e é . - O objetivo: mostrar que
, isto é, que existe um inteiro tal que .
Observação importante: aqui estamos assumindo
, porque a notação
(divisibilidade) só faz sentido usualmente para
não nulo.
Passo 2
Definição e consequência imediata de
.
Por definição de divisibilidade,
significa que existe um inteiro
tal que
Vou usar este
explicitamente nas etapas seguintes. Note que
é um número inteiro porque
,
,
são inteiros.
Passo 3
Uso do lema de Bézout (identidade de Bézout) para
.
Uma consequência fundamental da definição de máximo divisor comum (e do algoritmo de Euclides) é o seguinte: como
, existem inteiros
e
tais que
Isto é a identidade de Bézout. Aqui
e
são inteiros que dependem de
e
.
Passo 4
Multiplicar a identidade de Bézout por
.
Multiplicando a igualdade da Bézout por
obtemos
Cada termo desta igualdade é um inteiro, pois
são inteiros.
Passo 5
Substituir
usando a informação do Passo 2 e reorganizar.
Do Passo 2 temos
. Multiplicando ambos os lados por
(que é inteiro) dá
Substituindo esse termo na igualdade do Passo 4 encontramos
Agrupando fatores
,
Aqui
é um inteiro, sendo soma e produto de inteiros.
Passo 6
Conclusão final com interpretação de divisibilidade.
Da igualdade
conclui-se que
divide
, pois
é múltiplo de
. Ou seja, existe um inteiro (especificamente
) tal que
. Portanto finalmente provamos que
.
Um exemplo numérico rápido para fixar a ideia: tome
,
,
. Então
, e
porque
. A identidade de Bézout dá inteiros
tais que
; multiplicando por
e usando
obtemos que
divide
, como a prova afirma.