Prove que m d c(a, b)=m d c(a+k b, b) para todo inteiro k.

Passo 1

O enunciado pede para provar que, para quaisquer inteiros a, b e k, vale
\operatorname{mdc}(a,b)=\operatorname{mdc}(a+k b,b).
Informações dadas:
  • a é um inteiro;
  • b é um inteiro;
  • k é um inteiro;
  • A função \operatorname{mdc}(\cdot,\cdot) é o máximo divisor comum (positivo) entre os dois inteiros.
O que se pede: mostrar que adicionar a a um múltiplo inteiro de b não altera o máximo divisor comum com b.

Passo 2

Relembrando definições e uma propriedade básica que vamos usar (aula rápida e amigável):
  • Dizemos que d divide x e escrevemos d\mid x se existe um inteiro t tal que x = d t.
  • O máximo divisor comum \operatorname{mdc}(x,y) é o maior inteiro positivo que divide simultaneamente x e y.
  • Propriedade fundamental de divisibilidade: se d\mid r e d\mid s, então para quaisquer inteiros u,v vale d\mid (u r + v s). Isto é fácil de ver: se r = d r' e s = d s' então u r + v s = d(u r' + v s').
Essa propriedade é a ferramenta chave aqui: combinações inteiras de números divisíveis por d continuam divisíveis por d.

Passo 3

Mostro que qualquer divisor comum de a e b também divide a+k b.
Seja d tal que d\mid a e d\mid b. Pela propriedade anterior, para o inteiro k temos
d\mid (a + k b).
Explicando passo a passo: como d\mid a existe u com a = d u; como d\mid b existe v com b = d v. Então
a + k b = d u + k (d v) = d(u + k v),
logo d\mid (a+k b).
Portanto todo divisor comum de a e b é divisor comum de a+k b e b. Em notação de conjuntos:
\{d\in\mathbb{Z}_{>0} \mid d\mid a,\\ d\mid b\} \subseteq \{d\in\mathbb{Z}_{>0} \mid d\mid (a+k b),\\ d\mid b\}.

Passo 4

Agora a recíproca: qualquer divisor comum de a+k b e b também divide a.
Seja d tal que d\mid (a+k b) e d\mid b. Então, usando a combinação inteira com coeficientes 1 e -k,
a = (a+k b) - k b.
Como d\mid (a+k b) e d\mid b, pela propriedade das combinações inteiras temos d\mid a. Mais explicitamente: existem inteiros u,v com a+k b = d u e b = d v. Então
a = d u - k (d v) = d(u - k v),
portanto d\mid a.
Assim
\{d\in\mathbb{Z}_{>0} \mid d\mid (a+k b),\\ d\mid b\} \subseteq \{d\in\mathbb{Z}_{>0} \mid d\mid a,\\ d\mid b\}.

Passo 5

Das inclusões dos passos 3 e 4 segue que os conjuntos de divisores comuns de (a,b) e de (a+k b,b) coincidem. Como o máximo divisor comum é simplesmente o maior elemento positivo desse conjunto, os máximos também coincidem. Logo
\operatorname{mdc}(a,b)=\operatorname{mdc}(a+k b,b).
Comentário extra e motivacional (curto): isso significa que, na prática, ao calcular \operatorname{mdc} via algoritmo de Euclides, substituir a por a+k b 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!

Resposta

\operatorname{mdc}(a,b)=\operatorname{mdc}(a+k b,b)

Exercícios relacionados