For each of the following pairs a, b ? Z+, determine gcd(a, b) and express it as

Question

For each of the following pairs a, b ? Z+, determine gcd(a, b) and express it as a linear combination of a, b. a) 231, 1820 b) 1369, 2597 c) 2689, 4001

Explanation / Answer

a) 1820 - 7(231) = 203 231 - 1(203) = 28 203 - 7(28) = 7 28 - 4(7) = 0 ===> 203 - 7(28) = 7 => 203 - 7(231 - 1(203)) = 7 => 8(203) - 7(231) = 7 => 8(1820 - 7(231)) - 7(231) = 7 => 8(1820) - 63(231) = 7 b) 2597 - 1(1369) = 1228 1369 - 1(1228) = 141 1228 - 8(141) = 100 141 - 1(100) = 41 100 - 2(41) = 18 41 - 2(18) = 5 18 - 3(5) = 3 5 - 3 = 2 3 - 2 = 1 2 - 2(1) = 0 ===> 3 - (5 - 3) = 1 => 2(3) - 5 = 1 => 2(18 - 3(5)) - 5 = 1 => 2(18) - 7(5) = 1 => 2(18) - 7(41 - 2(18)) = 1 => 16(18) - 7(41) = 1 => 16(100 - 2(41)) - 7(41) = 1 => 16(100) -39(41) = 1 => 16(100) - 39(141 - 1(100)) = 1 => 55(100) - 39(141) = 1 => 55(1228 - 8(141)) - 39(141) = 1 => 55(1228) - 479(141) = 1 => 55(1228) - 479(1369 - 1(1228)) = 1 => 534(1228) - 479(1369) = 1 => 534(2597 - 1(1369)) - 479(1369) = 1 => 534(2597) - 1013(1369) = 1 c) 4001 - 1(2689) = 1312 2689 - 2(1312) = 65 1312 - 20(65) = 12 65 - 5(12) = 5 12 - 2(5) = 2 5 - 2(2) = 1 2 - 2(1) = 0 ===> 5 - 2(12 - 2(5)) = 1 => 5(5) - 2(12) = 1 => 5(65 - 5(12)) - 2(12) = 1 => 5(65) - 27(12) = 1 => 5(65) - 27(1312 - 20(65)) = 1 => 545(65) - 27(1312) = 1 => 545(2689 - 2(1312)) - 27(1312) = 1 => 545(2689) - 1117(1312) = 1 => 545(2689) - 1117(4001 - 1(2689)) = 1 => 1662(2689) - 1117(4001) = 1

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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