Linear combinations euclidean algoritm extended

• sg001
In summary, the Euclidean Algorithm can be used to find d= gcd(a,b) and x, y \in Z. The Attempt at a Solution provides a possible solution for finding ax+by.
sg001

Homework Statement

I have questions along the line of

Use the Euclidean Algorithm to find d= gcd(a,b) and x, y $\in$ $Z$ with d= ax +by

The Attempt at a Solution

Ok so I use the euclidean algorithm as I know it on say gcd (83,36), by minusing of the the lowest number and repeating until i get the last non zero remainder ie, the gcd but I am completely lost on how to find the form ax +by, I know there must be some technique other than guessing and trial and error...
anyone care to let me in?

Yes, 36 divides into 83 twice with remainder 11: (I) 11= 83- 2(36).

Then 11 divides into 36 three times with remainder 3: (II) 3= 36- 3(11).

3 divides into 11 three times with remainder 2: (III) 2= 11- 3(3).

Finally, 2 divides into 3 once with remainder 1: (IV) 1= 3- 2 which tells us that the least common denominator is 1. (36 and 83 are "relatively prime".)

Now replace the "2" in equation (IV) with "11- 3(3)" from (III) to get
1= 3- (11- 3(3))= 3- 11+ 3(3)= 4(3)- 11.

Then replace the "(3)" in that equation by "36- 3(11)" from (II) to get
1= 4(36- 3(11))- 11= 4(36)- 12(11)- 11= 4(36)- 13(11).

Finally, replace the "(11)" in that equation by "83- 2(36)" from (I) to get
1= 4(36)- 11(83- 2(36))= 4(36)- 11(83)+ 22(36)= 26(36)- 11(83).

That is "d= ax+ by" with d=1, a= -11, b= 26.

HallsofIvy said:
Yes, 36 divides into 83 twice with remainder 11: (I) 11= 83- 2(36).

Then 11 divides into 36 three times with remainder 3: (II) 3= 36- 3(11).

3 divides into 11 three times with remainder 2: (III) 2= 11- 3(3).

Finally, 2 divides into 3 once with remainder 1: (IV) 1= 3- 2 which tells us that the least common denominator is 1. (36 and 83 are "relatively prime".)

Now replace the "2" in equation (IV) with "11- 3(3)" from (III) to get
1= 3- (11- 3(3))= 3- 11+ 3(3)= 4(3)- 11.

Then replace the "(3)" in that equation by "36- 3(11)" from (II) to get
1= 4(36- 3(11))- 11= 4(36)- 12(11)- 11= 4(36)- 13(11).

Finally, replace the "(11)" in that equation by "83- 2(36)" from (I) to get
1= 4(36)- 11(83- 2(36))= 4(36)- 11(83)+ 22(36)= 26(36)- 11(83).

That is "d= ax+ by" with d=1, a= -11, b= 26.

Thanks that makes sense although I was hoping I could have acheived the result by ie gcd(83,36) =

83-36 =47 -36 = 36 -11 = 25 -11 = 14-11 = 11-3 = 8-3 = 5-3 = 3-2 = 2-1 = 1 !

and then I was hoping the coefficients would lie in there somewhere...

but I guess there's only some ways it will work

by the way how did you get the 13 in the fifth paragraph on the last expression?

1. What is a linear combination?

A linear combination is a mathematical operation that involves multiplying each term in a set of numbers by a constant and then adding the results together. For example, if we have the set {2, 3, 5}, a linear combination of this set could be 2(2) + 3(3) + 5(5) = 4 + 9 + 25 = 38.

2. What is the Euclidean algorithm?

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers. It involves repeatedly dividing the larger number by the smaller number and using the remainder as the new divisor until the remainder is equal to 0. The last non-zero remainder is the GCD.

3. How does the Euclidean algorithm work in extended form?

The extended form of the Euclidean algorithm involves keeping track of the quotients and remainders in each step of the algorithm. This allows us to find not only the GCD, but also the specific values of x and y in the equation ax + by = GCD(a, b).

4. What is the purpose of using linear combinations in the extended Euclidean algorithm?

The extended Euclidean algorithm uses linear combinations to find the coefficients x and y that satisfy the equation ax + by = GCD(a, b). This is useful in applications such as cryptography, where finding the GCD of two numbers is important for determining the encryption key.

5. What are some applications of the linear combinations extended Euclidean algorithm?

The linear combinations extended Euclidean algorithm has various applications in mathematics and computer science. It is commonly used in cryptography for finding encryption keys, in error-correcting codes, and in solving systems of linear equations. It also has applications in number theory, such as finding modular inverses and solving Diophantine equations.

Replies
1
Views
1K
Replies
1
Views
4K
Replies
1
Views
3K
Replies
4
Views
1K
Replies
2
Views
2K
Replies
1
Views
1K
Replies
20
Views
3K
Replies
1
Views
2K
Replies
11
Views
2K
Replies
5
Views
3K