Mostrar que se b mid c então (a+c, b)=(a, b)

Passo 1

Beleza, o enunciado é este: “Mostrar que se então .”
Conteúdo: estamos trabalhando com divisibilidade e o máximo divisor comum (MDC ou ).
O que precisamos:
  1. Entender a definição de – ou seja, o maior número que divide ao mesmo tempo e .
  2. Conhecer a propriedade de que, se um número divide dois outros, qualquer combinação linear deles também é dividida por esse número.
  3. Usar o fato dado de que , ou seja, para algum inteiro .

Passo 2

Vamos lembrar a definição de :
  • Um inteiro é se (i) divide e , e (ii) qualquer outro divisor comum de e também divide .

Passo 3

Primeira mão da prova (mostrar divide ):
  1. Seja . Por definição, e .
  2. Como , escrevemos .
  3. Então .
  4. Pela propriedade da divisibilidade, se e , então .
  5. Logo e , ou seja, é um divisor comum de e .
  6. Isso mostra que qualquer divisor comum de e (em particular ) também divide qualquer divisor comum de e , ou seja, .

Passo 4

Segunda mão da prova (mostrar divide ):
  1. Seja . Então e .
  2. De novo, como , temos .
  3. Se e , então .
  4. Logo . Como já tínhamos , concluímos que é divisor comum de e .
  5. Então .

Passo 5

Dos dois lados vimos que
gcd(a,b);<=;gcd(a+c,b) e gcd(a+c,b);<=;gcd(a,b)
Isso só pode ocorrer se forem iguais.

Resposta

boxedgcd(a+c,b)=gcd(a,b)

Exercícios relacionados