Demonstre que, se a ≡ b (mod. m) então mdc (a, m) = mdc (b, m).
Demonstração
Se a ≡ b (mod. m) então a = xm + r e b = ym + r. Assim, temos duas possibilidade:
Para r = 0, m é um divisor de a ⇒ mdc (a, m) = m.
Da mesma forma, m é um divisor de b ⇒ mdc (b, m) = m.
Dessa forma, concluímos que mdc(a, m) = m = mdc (b, m).
Para r ≠ 0, mdc (a, m) = mdc (m, r) e mdc (b, m) = mdc (m, r) de acordo com o algoritmo de Euclides ou processo das divisões sucessivas.
Dessa forma, mdc (a, m) = mdc (m, r) = mdc (b, m).
c.q.d.
Nenhum comentário:
Postar um comentário