Problem Set Worksheet Page 6
ADVERTISEMENT
1
2
3
4
5
6
7
8(c) gcd (119, 272) = 119x + 272y
We find gcd (119, 272) by using the Division Algorithm, and then “retracing our
steps.”
272 = q
119 + r
1
1
272 = (2) (119) + 34
(eq. 7)
Repeat for 119 and 34
119 = q
(34) + r
2
2
119 = (3) (34) + 17
(eq. 8)
Repeat for 34 and 17
34 = q
(17) + r
3
3
34 = (2) (17) + 0
gcd (119, 272) = last non-zero remainder
gcd (119, 272) = 17
So, we want x and y such that 119x + 272y = 17
From eq. 8 we have, 17 = 119 − (3) (34)
(eq. 9)
From eq. 7 we have, 34 = 272 − (2) (119)
Hence, eq. 9 becomes 17 = 119 − (3) (272 − (2) (119))
⇒ 17 = (7) (119) − (3) (272)
i.e., 119 (7) + 272 (−3) = 17
Our particular solution is (x
, y
) = (7, −3)
0
0
All other solutions are of the form
Ã
!
µ
¶
b
a
x = x
+
t;
y = y
−
t
for t ∈ Z
0
0
d
d
Hence, all solutions are of the form:
µ
¶
µ
¶
272
119
x = 7 +
t;
y = −3 −
t
for t ∈ Z
17
17
i.e., x = 7 + 16t;
y = −3 − 7t
for t ∈ Z
6
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education