Problem Set Worksheet
ADVERTISEMENT
1
2
3
4
5
6
7
8Problem Set 2.3; page 31
Fall 2004
Pat Rossi
Name
1. Find the gcd (143, 227) , gcd (306, 657) , gcd (272, 1479) .
We find all of these by using the Division Algorithm.
(a) gcd (143, 227)
277 = q
(143) + r
1
1
277 = (1) (143) + 134
Repeat with 143 and 134.
143 = q
(134) + r
2
2
143 = (1) (134) + 9
Repeat with 134 and 9.
134 = q
(9) + r
3
3
134 = (14) (9) + 8
Repeat with 9 and 8.
9 = q
(8) + r
4
4
9 = (1) (8) + 1
Repeat with 8 and 1.
8 = q
(1) + r
5
1
8 = (8) (1) + 0
gcd (143, 227) = last non-zero remainder
gcd (143, 227) = 1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education