Ask Singapore Homework?
Upload a photo of a Singapore homework and someone will email you the solution for free.
Question
International Baccalaureatte | Further Maths HL
One Answer Below
Anyone can contribute an answer, even non-tutors.
Need help with this question! Have gotten the gcd as 9, but I'm not too sure on how to express the integral linear combination part.
Date Posted: 3 years ago
Views: 627
You want to do this :
gcd(987654321,9999) = 987654321s + 9999t,
Where s and t are integers.
It's basically c = ax + by where c is your gcd, x and y are the two numbers, a and b are integer coefficients to be found.
(Notice that this is similar to y = mx + c, equation of straight line)
You will need to work backwards from your earlier part, which is ,
① 987654321 ÷ 9999 = 98775 R 3096
② 9999 ÷ 3096 = 3 R 711
③ 3096 ÷ 711 = 4 R 252
④ 711 ÷ 252 = 2 R 207
⑤ 252 ÷ 207 = 1 R 45
⑥ 207 ÷ 45 = 4 R 27
⑦ 45 ÷ 27 = 1 R 18
⑧ 27 ÷ 18 = 1 R 9
⑨ 18 ÷ 9 = 2
So gcd = 9
Start based on line ⑧
9 = 27 - 18
= 27 - (45 - 27) (based on line ⑦)
= 2 × 27 - 45
= 2 × (207 - 4 × 45) - 45 (based on line ⑥)
= 2 × 207 - 9 × 45
= 2 × 207 - 9 × (252 - 207) (based on line ⑤)
= 11 × 207 - 9 × 252
= 11 × (711 - 2 × 252) - 9 × 252 (based on line ④)
= 11 × 711 - 31 × 252
= 11 × 711 - 31 × (3096 - 4 × 711) (based on line ③)
= 135 × 711 - 31 × 3096
= 135 × (9999 - 3 × 3096) - 31 × 3096 (based on line ②)
= 135 × 9999 - 436 × 3096
= 135 × 9999 - 436 × (987654321 - 98775 × 9999) (based on line ①)
= 43066035 × 9999 - 436 × 987654321
Here your s = -436 and t = 43066035
gcd(987654321,9999) = 987654321s + 9999t,
Where s and t are integers.
It's basically c = ax + by where c is your gcd, x and y are the two numbers, a and b are integer coefficients to be found.
(Notice that this is similar to y = mx + c, equation of straight line)
You will need to work backwards from your earlier part, which is ,
① 987654321 ÷ 9999 = 98775 R 3096
② 9999 ÷ 3096 = 3 R 711
③ 3096 ÷ 711 = 4 R 252
④ 711 ÷ 252 = 2 R 207
⑤ 252 ÷ 207 = 1 R 45
⑥ 207 ÷ 45 = 4 R 27
⑦ 45 ÷ 27 = 1 R 18
⑧ 27 ÷ 18 = 1 R 9
⑨ 18 ÷ 9 = 2
So gcd = 9
Start based on line ⑧
9 = 27 - 18
= 27 - (45 - 27) (based on line ⑦)
= 2 × 27 - 45
= 2 × (207 - 4 × 45) - 45 (based on line ⑥)
= 2 × 207 - 9 × 45
= 2 × 207 - 9 × (252 - 207) (based on line ⑤)
= 11 × 207 - 9 × 252
= 11 × (711 - 2 × 252) - 9 × 252 (based on line ④)
= 11 × 711 - 31 × 252
= 11 × 711 - 31 × (3096 - 4 × 711) (based on line ③)
= 135 × 711 - 31 × 3096
= 135 × (9999 - 3 × 3096) - 31 × 3096 (based on line ②)
= 135 × 9999 - 436 × 3096
= 135 × 9999 - 436 × (987654321 - 98775 × 9999) (based on line ①)
= 43066035 × 9999 - 436 × 987654321
Here your s = -436 and t = 43066035
See 1 Answer
See question main comments for explanation.
360 Tutoring Program