Euclidean Algorithm - Linear Combination
Problem:
Use the Euclidean Algorithm, find the gcd of 330 and 126 and write it as a linear combination of the two numbers.
===============
Attempt:
Using the Euclidean Algorithm, we need to find (330, 126)
330 = 126 * 2 + 78 (5)
126 = 78 * 1 + 48 (4)
78 = 48 * 1 + 30 (3)
30 = 18 * 1 + 12 (2)
18 = 12 * 1 + 6 (1)
12 = 6 * 2 + 0, Thus the gcd = 6. As a result, (330, 126)= 6.
Following the extended Euclidean Algorithm, so I do it solve for '6' backwards.
From (1), 18 = 12 * 1 + 6. I solve for 6. Thus
6 = 18 - 12 * 1 (A)
From (2), solve for 12, we get
12 = 30 - 18 * 1 (B)
Plug 12 from (B) to A we get 6 = 18 - (30 - 18*1)
Likewise, we get
6 = 18 - (30 - (48 - 30))... and so on.
where I need to get it in the form
6 = 330x + 126y, where x and y are integers.
==================
Is there a way to find the linear combination faster or better? Thank you.
