The Division Algorithm

Let \(a\) and \(b\) be nonzero integers. If there exist integers \(r\) and \(s\) such that \(ar + bs = 1\), show that \(a\) and \(b\) are relatively prime.

\(Proof.\) Suppose \((a, b) = d > 1\), we have \(a = dh\) and \(b = dk\), then \[1 = ar + bs = dhr + dbs = d(hr + bs).\] So \(d\) must devide \(1\). Hence, \(a\) and \(b\) are relatively prime. \(\blacksquare\)

Let \(a\) and \(b\) be integers such that \(\text{gcd}(a, b) = 1\). Let \(r\) and \(s\) be integers such that \(ar + bs = 1\). Prove that

\[\text{gcd}(a, s) = \text{gcd}(r, b) = \text{gcd}(r, s) = 1.\]

\(Proof.\) Suppose \(\text{gcd}(a, s)\), then \(b = b(ar + bs) = bra + bbs\), thus \(d | b\), contradict the fact that \(\text{gcd}(a, b) = 1\), thus \(\text{gcd}(a, s) = 1\).

Similarly, \(\text{gcd}(r, b) = 1\).

Obviously, \(\text{gcd}(r, s) = 1\). \(\blacksquare\)