 ## Question

International Baccalaureatte | Further Maths HL

Anyone can contribute an answer, even non-tutors.

##### Huixian

chevron_right chevron_right

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: 2 years ago
Views: 537
J
2 years ago
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 