Proof That ca ≡ cb (mod m) If And Only If a ≡ b (mod m/(c, m))

Let \(ca ≡ cb \bmod m\) and let \(d = (c, m)\):

$$\begin{align} m | (ca - cb) &\implies m | c(a - b) \\ &\implies (m/d) | (c/d) (a - b) \end{align}$$

Since \(d\) is the gcd, then \((m/d, c/d) = 1\). So:

$$ m/d | (a - b) \implies a ≡ b \mod (m/d) $$

Therefore, \(ca ≡ cb \bmod m\) implies \(a ≡ b \bmod (m/d)\). As for \(a ≡ b \bmod (m/d)\) implying \(ca ≡ cb \bmod m\):

$$\begin{align} a ≡ b \bmod (m/d) &\implies (m/d) | (a - b) \\ &\implies m | da - db \\ &\implies m | (c/d)(da - db) \\ &\implies m | ca - cb \end{align}$$

This means \(ca ≡ cb \bmod m\).

Proof That ca ≡ cb (mod m) If And Only If a ≡ b (mod m/(c, m))

Styles

Proof That ca ≡ cb (mod m) If And Only If a ≡ b (mod m/(c, m))

Styles