Seja
. Mostre que:
Passo 1
O enunciado dá
e pede para mostrar que
ou seja, que o máximo divisor comum entre
e
é
.
Informações relevantes dadas:
- Um inteiro natural
qualquer. - Os dois números cujos divisores comuns queremos analisar são
e .
Passo 2
Lembra do truque básico do algoritmo de Euclides (e de uma propriedade simples do MDC): para inteiros
e qualquer inteiro
vale
Explicando por que isso é verdade (aula rápida): se
divide
e
então
divide
(pois
é combinação linear de
e
). Reciprocamente, se
divide
e
então
divide
. Logo os conjuntos de divisores comuns de
e de
coincidem, assim seus maiores divisores comuns são iguais.
Passo 3
Aplicamos essa propriedade com
,
e
. Calculamos:
Portanto, pelo passo anterior,
Passo 4
Agora aplicamos novamente a mesma ideia para reduzir
. Subtraindo
vezes
de
temos
Pelo mesmo raciocínio do algoritmo de Euclides,
Passo 5
Mas para qualquer inteiro
vale
, pois
divide todos os inteiros e não existe divisor comum maior que
. Então, juntando as igualdades:
Como bônus didático, nota-se explicitamente a identidade de Bézout que prova que o MDC é
: a partir das operações acima obtemos
o que mostra que
é combinação inteira de
e
, logo o MDC é
.
Passo 6
Resumo em linguagem amiga: subtraindo
vezes
de
aparece o
; subtraindo
vezes
de
aparece
. Isso reduz o problema até o caso evidente
. Portanto os dois números são primos entre si para todo
. Força aí — é esse tipo de truque com o algoritmo de Euclides que cai muito na prova!