use the Euclidean algorithm to express gcd(94, 159) as a linear combination of 94 and 159

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Lets write Euclidean algorithm first.

159=1*94+65

94=1*65+29

65=2*29+7

29=4*7+1

7=7*1+0

So gcd(94, 159)=1, now we replace 1 in the last step as gcd and go back.

gcd=29-4*7=29-4*(65-2*29)=9*29-4*65=9*(94-65)-4*65=9*94-13*65=9*94-13*(159-94)=22*94-13*159

So answer is 22*94-13*159.