Problem Set Worksheet Page 5
ADVERTISEMENT
1
2
3
4
5
6
7
8(b) gcd (24, 138) = 24x + 138y
We find gcd (24, 138) by using the Division Algorithm, and then “retracing our
steps.”
138 = q
(24) + r
1
1
138 = (5) (24) + 18
(eq. 4)
Repeat using 24 and 18.
24 = q
(18) + r
2
2
24 = (1) (18) + 6
(eq. 5)
Repeat using 18 and 6.
18 = q
(6) + r
3
3
18 = (3) (6) + 0
gcd (24, 138) = last non-zero remainder
gcd (24, 138) = 6
So, we want x and y such that 24x + 138y = 6
From eq. 5 we have, 6 = 24 − (1) (18)
(eq. 6)
From eq. 4, we have, 18 = 138 − (5) (24)
Thus, eq. 6 becomes 6 = 24 − (1) (138 − (5) (24))
⇒ 6 = (6) (24) − (1) (138)
i.e., 24 (6) + 138 (−1) = 6
Our particular solution is (x
, y
) = (6, −1)
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:
µ
¶
µ
¶
138
24
x = 6 +
t;
y = −1 −
t
for t ∈ Z
6
6
i.e., x = 6 + 23t;
y = −1 − 4t
for t ∈ Z
5
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education