Problem Set Worksheet Page 7
ADVERTISEMENT
1
2
3
4
5
6
7
8(d) gcd (1769, 2378) = 1769x + 2378y
We find gcd (1769, 2378) by using the Division Algorithm, and then “retracing
our steps.”
2378 = q
(1769) + r
1
1
2378 = (1) (1769) + 609
(eq. 10)
Repeat for 1769 and 609
1769 = q
(609) + r
2
2
1769 = (2) (609) + 551
(eq. 11)
Repeat with 609 and 551
609 = q
(551) + r
3
3
609 = (1) (551) + 58
(eq. 12)
Repeat with 551 and 58
551 = q
(58) + r
4
4
551 = (9) (58) + 29
(eq. 13)
Repeat with 58 and 29
58 = q
(29) + r
5
5
58 = (2) (29) + 0
gcd (1769, 2378) = last non-zero remainder
gcd (1769, 2378) = 29
So, we want x and y such that 1769x + 2378y = 29
From eq. 13 we have, 29 = 551 − (9) (58)
(eq. 14)
From eq. 12 we have, 58 = 609 − (1) (551)
Hence, eq. 14 becomes 29 = 551 − (9) (609 − (1) (551))
⇒ 29 = (−9) (609) + (10) (551)
(eq. 15)
From eq. 11 we have , 551 = 1769 − (2) (609)
Thus, eq. 15 becomes 29 = (−9) (609) + (10) (1769 − (2) (609))
⇒ 29 = (−29) (609) + (10) (1769)
(eq. 16)
From eq. 10 we have, 609 = 2378 − (1) (1769)
Hence, eq. 16 becomes 29 = (−29) (2378 − (1) (1769)) + (10) (1769)
⇒ 29 = (−29) (2378) + (39) (1769)
i.e., 1769 (39) + 2378 (−29) = 29
Our particular solution is (x
, y
) = (39, −29)
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:
µ
¶
µ
¶
2378
1769
x = 39 +
t;
y = −29 −
t
for t ∈ Z
29
29
i.e., x = 39 + 82t;
y = −29 − 61t
for t ∈ Z
7
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education