Prove que mdc(a+b, a-b) >= mdc(a, b), para quaisquer a, b in Z.

Passo 1

O enunciado nos pede para mostrar que, para quaisquer a,binZ, vale
gcd(a+b,a-b)>= gcd(a,b).
O conteúdo principal aqui é a propriedade de que todo divisor comum de dois números também divide qualquer combinação linear inteira desses números.

Passo 2

Seja d = gcd(a,b).
Por definição de máximo divisor comum, temos
  1. d divide a, isto é, existe kinZ tal que a = d,k.
  2. d divide b, isto é, existe ellinZ tal que b = d,ell.

Passo 3

Como d divide tanto a quanto b, ele divide qualquer combinação linear inteira de a e b. Em particular:
  • d divide a+b (caso 1cdot a + 1cdot b).
  • d divide a-b (caso 1cdot a + (-1)cdot b).

Passo 4

Logo, d é um divisor comum de a+b e a-b. Mas a definição de máximo divisor comum nos diz que
gcd(a+b,a-b)
é o maior inteiro que divide simultaneamente a+b e a-b.
Como d é um desses divisores, segue
gcd(a+b,a-b),>=,d,

Resposta

Portanto
gcd(a+b,a-b),>=,gcd(a,b),
como queríamos provar.

Exercícios de Livros Relacionados