Find GCD(a, b) and find particular solutions to ax + by = GCD(a, b) for the foll

Question

Find GCD(a, b) and find particular solutions to ax + by = GCD(a, b) for the following pairs of integers (a, b): (You must show all your steps as in the lecture videos to receive full credit) [10 points each] (a) (656,294) (b) (166361,4043)

Please show FULL work. CLEARLY. thanks. Find GCD(a, b) and find particular solutions to ax + by = GCD(a, b) for the following pairs of integers (a, b): (You must show all your steps as in the lecture videos to receive full credit) [10 points each] (a) (656,294) (b) (166361,4043)

Please show FULL work. CLEARLY. thanks. Find GCD(a, b) and find particular solutions to ax + by = GCD(a, b) for the following pairs of integers (a, b): (You must show all your steps as in the lecture videos to receive full credit) [10 points each] (a) (656,294) (b) (166361,4043)

Please show FULL work. CLEARLY. thanks.

Explanation / Answer

GCD can be calculated using Euclid's Algorithm.

(a)(656,294)

Lets set up a division problem where a>b.

a ÷ b = c with remainder R.

Divide and then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.

656 ÷ 294 = 2 R 68    (656 = 2 × 294 + 68)

294 ÷ 68 = 4 R 22    (294 = 4 × 68 + 22)

68 ÷ 22 = 3 R 2    (68 = 3 × 22 + 2)

22 ÷ 2 = 11 R 0    (22 = 11 × 2 + 0)

When remainder R = 0, the GCF is the divisor, b, in the last equation. GCF = 2

(b) (166361,4043)

Set up a division problem where a> b.
a ÷ b = c with remainder R.

Divide and then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.

166361 ÷ 4043 = 41 R 598    (166361 = 41 × 4043 + 598)

4043 ÷ 598 = 6 R 455    (4043 = 6 × 598 + 455)

598 ÷ 455 = 1 R 143    (598 = 1 × 455 + 143)

455 ÷ 143 = 3 R 26    (455 = 3 × 143 + 26)

143 ÷ 26 = 5 R 13    (143 = 5 × 26 + 13)

26 ÷ 13 = 2 R 0    (26 = 2 × 13 + 0)

When remainder R = 0, the GCD is the divisor, b, in the last equation. GCD = 13


Hope it helped.Kindly upvote!

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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