3. Let g be the greatest common factor of a 2,637,110,736 and b 2,961,110,016. (
ID: 3146493 • Letter: 3
Question
3. Let g be the greatest common factor of a 2,637,110,736 and b 2,961,110,016. (a) Find g using Euclid's algorithm, and b) using one of the techniques shown in lectures, find suitable integers and y to satisfy the equation 2,961,110.0162 + 2,637,1 10.736 y. g Find integers s and t such that 527,7602,961,110,016 s 2,637,110,736t. Don't just give a single s and t, but find all pairs of integers (s, t) that satisfy this equation. the given equation. If you haven't done so, then do it here, as if a separate task. Explain any difficulties you encountered while doing such a check, and how you overcame them. (d) As part of your answer to part (c) you should check that the numbers you have found do indeed satisfyExplanation / Answer
(Note: Techinques shown in lectures are not given and therefore, only Euclid's algorithm will be used.)
(a) a = 2637110736
b = 2961110016
2961110016 = 2637110736 + 323999280
2637110736 = 8*323999280 + 45116496
323999280 = 7*45116496 + 8183808
45116496 = 5*8183808 + 4197456
8183808 = 4197456 + 3986352
4197456 = 3986352 + 211104
3986352 = 18*211104 + 186480
211104 = 186480 + 24624
186480 = 7* 24624 + 14112
24624 = 14112 + 10512
14112 = 10512 + 3600
10512 = 2*3600 + 3312
3600 = 3312 + 288
3312 = 11*288 + 144
288 = 2*144 + 0
The gcd is g = 144.
(b) Because the techniques used in lectures are not given, it is not possible to know which method to use. Nevertheless answer is below. This will be verified in (d).
x = 9860829 and y = -8781875.
(c) 6768 = 144 * 47.
Thus 6768 is a multiple of g.
527760 = 144 * 3665.
We have from (b), x = 9860829 and y = -8781875.
s = 3665 * 9860829 and t = 3665 * -8781875
=> s = 36139938285 and t = -32185571875.
General solution according to Diophantine is
s = 36139938285 + k * 2961110016 / 144 and t = -32185571875 - k * 2637110736
=> s = 36139938285 - 20563264k and t = -32185571875 - 18313269k.
(d) We have from (c)
s = 36139938285 and t = -32185571875.
=> as + bt = 2637110736 * 36139938285 + 2961110016 * -32185571875 = 95305019249750927760 - 95305019249750400000 = 527760.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.