# Euclidean Algorithm - Linear Combination

• Sep 26th 2008, 06:11 AM
Paperwings
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.
• Sep 26th 2008, 06:27 AM
Jhevon
Quote:

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.

see post #8 here. i described the method you're using and a method that i think is better/faster. with this method, you find the gcd and the linear combination all in one shot
• Sep 26th 2008, 12:04 PM
Paperwings
Thanks Jhevon. I'll give it a try.