Prove que
para todo inteiro
.
Passo 1
O enunciado pede para provar que, para quaisquer inteiros
,
e
, vale
Informações dadas:
-
é um inteiro; -
é um inteiro; -
é um inteiro; - A função
é o máximo divisor comum (positivo) entre os dois inteiros.
O que se pede: mostrar que adicionar a
um múltiplo inteiro de
não altera o máximo divisor comum com
.
Passo 2
Relembrando definições e uma propriedade básica que vamos usar (aula rápida e amigável):
- Dizemos que
divide e escrevemos se existe um inteiro tal que . - O máximo divisor comum
é o maior inteiro positivo que divide simultaneamente e . - Propriedade fundamental de divisibilidade: se
e , então para quaisquer inteiros vale . Isto é fácil de ver: se e então .
Essa propriedade é a ferramenta chave aqui: combinações inteiras de números divisíveis por
continuam divisíveis por
.
Passo 3
Mostro que qualquer divisor comum de
e
também divide
.
Seja
tal que
e
. Pela propriedade anterior, para o inteiro
temos
Explicando passo a passo: como
existe
com
; como
existe
com
. Então
logo
.
Portanto todo divisor comum de
e
é divisor comum de
e
. Em notação de conjuntos:
Passo 4
Agora a recíproca: qualquer divisor comum de
e
também divide
.
Seja
tal que
e
. Então, usando a combinação inteira com coeficientes
e
,
Como
e
, pela propriedade das combinações inteiras temos
. Mais explicitamente: existem inteiros
com
e
. Então
portanto
.
Assim
Passo 5
Das inclusões dos passos 3 e 4 segue que os conjuntos de divisores comuns de
e de
coincidem. Como o máximo divisor comum é simplesmente o maior elemento positivo desse conjunto, os máximos também coincidem. Logo
Comentário extra e motivacional (curto): isso significa que, na prática, ao calcular
via algoritmo de Euclides, substituir
por
não muda o resultado — e é exatamente essa invariância que o algoritmo explora quando faz subtrações sucessivas ou usa o resto da divisão. Você conseguiu entender a ideia central: divisores “sobrevivem” a somar múltiplos do outro número. Força aí nos estudos!