Prove que se b equiv c(bmod m), então mdc(b, m)=mdc(c, m).

Passo 1

O enunciado pede para provar que, se
bequiv cpmod m,
então
Conteúdo: congruência modular e máximo divisor comum (mdc).
O que vamos usar:
  1. Definição de congruência: mdc(b,m)=mdc(c,m).
  2. Definição de mdc: é o maior inteiro que divide simultaneamente bequiv cpmod miff mmid(b-c) e mdc(x,y).
  3. Propriedade básica de divisores: se x e y, então dmid x.

Passo 2

Já que bequiv cpmod m, temos mmid (b-c). Logo existe um inteiro k tal que
b - c = k,mLongrightarrow b = c + k,m
Agora, seja d um divisor comum de b e m.
1. dmid b e dmid m.
2. Então, pela propriedade de divisores, dmid(b - k,m).
3. Mas b - k,m = c, logo dmid c.
Isso mostra: todo divisor comum de (b,m) também divide c. Em particular, o maior deles, que é , também é divisor comum de mdc(b,m). Assim

Passo 3

O raciocínio inverso é igualzinho. Partimos de
c = b - k,m,
e tomamos d' divisor comum de c e m. Então
1. d'mid c e d'mid m.
2. Pela mesma propriedade, d'mid(c + k,m) = b.
Logo todo divisor comum de (c,m) divide b, e o maior deles satisfaz

Passo 4

Temos as duas desigualdades

Quando dois números satisfazem isso, eles são iguais.

Resposta

Exercícios relacionados