Problem Set Worksheet Page 2

ADVERTISEMENT

(b) gcd (306, 657)
657 = q
(306) + r
1
1
657 = (2) (306) + 45
Repeat with 306 and 45
306 = q
(45) + r
2
2
306 = (6) (45) + 36
Repeat with 45 and 36
45 = q
(36) + r
3
3
45 = (1) (36) + 9
Repeat with 36 and 9.
36 = q
(9) + r
4
4
36 = (4) (9) + 0
gcd (306, 657) = the last non-zero remainder.
gcd (306, 657) = 9
2

ADVERTISEMENT

00 votes

Related Articles

Related forms

Related Categories

Parent category: Education
Go
Page of 8