PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!! Let a and b be integers such

Question

PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!!

Let a and b be integers such that at least one of a and b is not zero. If a = bq + r, . then ged(a, b) ged(b, r). Suggestion: By Theorem 38, we have ged(b, r) is the smallest number in a certain set. Now use some easy arithmetic to show that ged(a, b) is a number in that set., too. W h at can you conclude? Again by Theorem 38. we have that ged(a, b) is th e smallest number in a certain set. Show that god(b, r) is in that set, too. What can you conclude?

Explanation / Answer

Suppose c is a common divisor of a and b. Then a = cs and b = ct for some s, t belong Z. Consequently, r = a - bq = cs- (ct)q = c(s -tq) . Hence c divides r ands so c is a common divisor of b and r. On the other hand, suppose e is a common divisor of b and r. Then b = ex, r = ey, and a = bq +r = (ex)q + ey = e(xq + y) . So e divides a, and thus e is a common divisor of a and b. Therefore, the set S of all common divisors of a and b is the same as the set T of all common divisors of b and r. Hence, GCD(a, b) = Max(S) =Max(T) = GCD(b, r)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.