If (a ≡ b mod m), (c ≡ d mod m), c|a And d|b, Then (a/c ≡ b/d mod m)

Since \(a ≡ b \bmod m\) and \(c ≡ d \bmod m\):

$$\begin{gather} mk = b - d \\ ml = d - c \end{gather}$$

Since \(c|a\) and \(d|b\):

$$\begin{gather} cx = a \implies x = a/c \\ dy=b \implies y=b/d \end{gather}$$

We can multiply \(xy\) to both sides of \( ml = d - c\):

$$\begin{align} mlxy = dxy - cxy \implies &mu = vx - zy \\ &mu = v(a/c) - z(b/d) \end{align}$$

This means \(\frac{a}{c} ≡ \frac{b}{d} \bmod m\).

Styles

(uses cookies)