Olimpíadas ⇒ Teoria dos Números - Congruências Tópico resolvido

[NãoCriativo]

Se mdc(k, m) = d, então ka ≡ kb (mod m) ⇔ a ≡ b (mod m/d)

Alguém sabe demonstrar esse teorema? Tentei postar esse problema na seção "Demonstrações", mas estava fechada.

[rodBR]

Demonstração: Como o [tex3]mdc(k,m) = d por definição , temos[/tex3]
[tex3]k =dk^{'} ,[/tex3] [tex3]m =dm^{'}[/tex3] [tex3]e[/tex3] [tex3]mdc(k^{'},m^{'}) =1.[/tex3]
[tex3]ka ≡kb(mod[/tex3] m)[tex3] , pela definição de congruência , temos[/tex3]
[tex3]m|kb-ka \rightarrow m|k(b-a)[/tex3]
[tex3]Isso equivale , a:[/tex3]
[tex3]dm^{'}[/tex3]|d [tex3]k^{'}(b-a) ⟺ m^{'}|k^{'}(b-a)[/tex3]
[tex3]Como o mdc(m^{'},k^{'})=1,e[/tex3] m=[tex3]dm^{'} ⟺[/tex3] m'[tex3]=\frac{m}{d} , Teremos[/tex3]
[tex3]\frac{m}{d}|b-a , isso quer dizer que b-a é um múltiplo de \frac{m}{d} . Por definição , isso é equivalente a:[/tex3]
a≡b(mod [tex3]\frac{m}{d}[/tex3]) [tex3]∎[/tex3]