Answer to Question #225080 in Combinatorics | Number Theory for Zara Hussain

Question

Show that if n ∣ m, where n and m are integers greater than 1, and if a ≡ b (mod m), where a and b are integers, then a ≡ b (mod n).

Answer 1

If $a ≡ b (mod\ m)$ , where $a$ and $b$ are integers, then $m|(a-b),$ that is $a-b=mt$ for some integer $t.$ Since $n|m,m=nk$ for some integer $k.$ Then $a-b=(nk)t=n(kt),$ and hence $n|(a-b).$ We conclude that $a ≡ b (mod\ n).$