Originally Posted by

**Paperwings** 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.