If gcd(a, m) = 1 And gcd(b, m) = 1, Then gcd(ab, m) = 1

Since gcd(a, m) = 1 and gcd(b, m) = 1:

$$ax+my=1$$$$bw+mz=1$$

Rearrange:

$$ax=1-my$$$$bw=1-mz$$

Multiply them:

$$\begin{align} (ax)(bw) & = (1-my)(1-mz) \\ & =(1-my-mz+m^2yz) \end{align}$$

Simplify:

$$ ab(xw)=1+m(-y-z+myz) $$$$ 1=ab(xw)+m(y+z-myz) $$

Since 1 = ab(j)+m(k), then gcd(ab, m) = 1.

Styles

(uses cookies)