Seja
. Mostre que:
Passo 1
O enunciado dá
e pede para mostrar que
.
Informações relevantes:
Informações relevantes:
- Dois números inteiros
e têm máximo divisor comum denotado por . - Queremos provar que o maior divisor comum entre
e é .
Passo 2
Lembrete útil (definição e propriedade básica de divisibilidade).
- Dizemos que um inteiro
divide um inteiro se existe inteiro tal que . Escreve-se . - Propriedade importante: se
e , então divide qualquer combinação linear inteira (com ). Isto é, . Vou usar essa propriedade logo a seguir. Expliquei porque: se e , então , um múltiplo de .
Passo 3
Calcule a combinação linear simples que conecta os dois números dados. Faça a subtração
Desenvolvendo
obtemos
. Então
Portanto encontramos a identidade inteira
Passo 4
Use a identidade com a propriedade de divisibilidade. Seja
qualquer divisor comum de
e
. Então
e
. Pela propriedade de combinações lineares,
divide
mas pela Passo 3 esse número é
. Logo
.
Passo 5
Conclua sobre
. Se um inteiro
divide
, então
. Como estamos falando de divisores positivos ao considerar o máximo divisor comum, qualquer divisor comum positivo deve ser
. Assim o maior divisor comum entre
e
é
.
Passo 6
(Argumento alternativo curto, equivalente, via algoritmo de Euclides) Ao dividir
por
nota-se que
. Substituindo,
portanto o resto da divisão é
. Pelo algoritmo de Euclides isso implica
. Mesmo resultado, outra visão.