If a ≡ b mod m And n|m, Then a ≡ b mod n

If \(a ≡ b \bmod m\), then there is an integer \(k\) such that:

$$ mk = b - a $$

If \(n|m\), then there is an integer \(q\) such that:

$$ qn = m $$

substituting \(m\):

$$\begin{aligned} (qn)k &= b - a \\ n(qk) &= b - a \implies a ≡ b \bmod n \end{aligned}$$

Styles

(uses cookies)