Show that if GCD(a, c) = 1 and c | ab, then c | b.ExerciseComplete the following proof. Le...

Show that if GCD(a, c) = 1 and c | ab, then c | b.

Exercise

Complete the following proof. Let a and b be integers. If p is a prime and p | ab, then p | a or p | b. We need to show that if p  a, then p must divide b. If p  a, then GCD(a, p) = 1, because _____ By Theorem 1, we can write 1 = sa + tp for some integers s and t. Then b = sab + tpb. (Why?) Then p must divide sab + tpb, because _____ So p | b. (Why?)

Theorem 1

If d is GCD(a, b), then

(a) d = sa+tb for some integers s and t. (These are not necessarily positive.)

---

(b) If c is any other common divisor of a and b, then c | d.

Proof

Let x be the smallest positive integer that can be written as sa + tb for some integers s and t, and let c be a common divisor of a and b. Since c | a and c | b, it follows from Theorem 2 that c | x, so c ≤ x. If we can show that x is a common divisor of a and b, it will then be the greatest common divisor of a and b and both parts of the theorem will have been proved. By Theorem 3, a = qx + r with 0 ≤ r. Solving for r, we have

r = a − qx = a − q(sa + tb) = a − qsa − qtb = (1 − qs)a + (−qt)b.

If r is not zero, then since r and r is the sum of a multiple of a and a multiple of b, we will have a contradiction to the fact that x is the smallest positive number that is a sum of multiples of a and b. Thus r must be 0 and x | a. In the same way we can show that x | b, and this completes the proof.

Theorem 2

Let a, b, and c be integers.

(a) If a | b and a | c, then a | (b + c).

---

(b) If a | b and a | c, where b > c, then a | (b − c).

---

(c) If a | b or a | c, then a | bc.

---

(d) If a | b and b | c, then a | c.

Proof

(a) If a | b and a | c, then b = k1a and c = k2a for integers k1 and k2. So b + c = (k1 + k2)a and a | (b + c).

---

(b) This can be proved in exactly the same way as (a).

---

(c) As in (a), we have b = k1a or c = k2a. Then either bc = k1ac or bc = k2ab, so in either case bc is a multiple of a and a | bc.

---

(d) If a | b and b | c, we have b = k1a and c = k2b, so c = k2b = k2(k1a) = (k2k1)a and hence a | c.

Theorem 3

If n and m are integers and n > 0, we can write m = qn + r for integers q and r with 0 ≤ r. Moreover, there is just one way to do this.