Matemática discreta| aritmética modular| mdc

Considere a, b, m Z com m maior ou igua a 2. Prove que se a = b(mod m), então mdc(a, m) = mdc(b, m).

Solução.

Considere p = mdc(a,b) e q = mdc(b,m).

Dado que a = b (mod m), então existe k inteiro tal que:  a = b + km.
Dado que q | b, e q | m, segue-se que q | a. Logo, pela definição de  q ? p.

Dado que a = b (mod m), então existe k' inteiro tal que:  b = a + k'm.
Dado que p | a, e p | m, segue-se que p | b. Logo, pela definição de  p ? q.

Portanto, q = p, isto é, mdc(a,b) = mdc(b,m).

Para mais informação:
asesor.matematica.1990@gmail.com
Whatsapp: (11) 994414817