Answer to Question #268518 in Discrete Mathematics for Micah

Question

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

Answer 1

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.