If (a ≡ b mod m and n|m), then a ≡ b mod nm

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)