Question

Find GCD for a and b using Euclidean Algorithm.let a = 427, b = 154 d = sa + tb

Answer 1

Here is my solutions:
427 = 2 (154 )+ 119
154 = 1 (119) + 35
119 = 3 (35) + 14
35 = 2 (14) + 7
14 = 2 (7) + 0
d = GCD (427, 154) = 7
d = sa + tb
35 = 2 (14) + 7
7 = 35 - 2 [14]
7 = 35 - 2 [119 - 3 [35]]
7 = 35 - 2 [119 - 3[154-119]]
7 = 35 - 2[119] + 6[154-119]]
7 = [154-119] - 2[119] + 6[154] - 6[119]
7 = [154-119] -8[119] + 6[154]
7 = 7[154] -9[427-2[154]]
7 = 7[154] -9[427] + 18[154]
7 = 25[154] - 9[427]
By comparing:
d = sa + tb
a = -9
b = 25
Do anyone using more simple ways to find GCD method.