The Division Algorithm

1. Exercises

1. Let \(d = \text{gcd}(a,b)\) and \(h\) is a common divisor of \(a\) and \(b\). Prove that \(h\) divide \(d\).
   

   \(Proof.\) Suppose \(a = mh\), \(b = nh\), then \[d = ra + sb = rmh + snh = h(rm + sn) \qed\]

2. 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\)

3. 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) = d \not = 1\), 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\)

4. Prove there eixsts a unique least common multiple for any two integers \(a\) and \(b\).
   

   \(Proof.\) Let \(l := \frac{ab}{\text{gcd}(a, b)}\), obviously it is a common multiple of \(a\) and \(b\).

   If \(a\) and \(b\) divide \(n\), then \(n = ra = sb = rpg = sqg\) where \(g = gcd(m, n)\). \(rp = sq \Rightarrow p | sq \Rightarrow p | s\) because \(\text{gcd}(p, q) = 1\), so \(l = \frac{ab}{g} = pqg | sqg = n\), thus \(l\) is the least common multiple of \(a\) and \(b\).

   If \(l^{'}\) is another least common multiple of \(a\) and \(b\), then \(l | l^{'}\) and \(l^{'} | l\), thus, \(l = l^{'}\).

   Hence, for any two integers \(a\) and \(b\), \(\frac{ab}{\text{gcd}(a, b)}\) is the least common multiple of them. \(\blacksquare\)

5. If \(d = \text{gcd}(a, b)\) and \(m = lcm(a, b)\), prove that \(dm = |ab|\).
   

   \(Proof.\) It's obvious according to 1.4.

6. Let \(p \geq 2\). Prove that if \(2^p -1\) is prime, then \(p\) must also be prime.
   

   \(Proof.\) Suppose \(p = mn\) and \(m \leq n\).

   \(2^{mn} - 1 = (2^m - 1)(2^{mn - m} + 2 ^{mn - 2m} + \cdots + 2^m + 2^0)\)

   If \(2^p - 1\) is prime, then \(2^m - 1 = 1\), thus \(m = 1\) and \(n = p\) so \(p\) must also be prime. \(\blacksquare\)