Question

find the solution for gcd(119,378)=119x+378y using Euclidean algorithm​

Answer 1

Answer:

8326 is the correct answer

Answer 2

we have to find the solution for GCD(119, 378) = 119x + 378y using Euclidean algorithm.

solution : by Euclidean division algorithm,

378 = 3 × 119 + 21

119 = 5 × 21 + 14

21 = 1 × 14 + 7

14 = 2 × 7 + 0

Therefore 7 is GCD of 119 and 378.

so, GCD(119 , 378) = 119x + 378y = 7

now 7 = 119x + 378y

⇒7 = 7 × 13x + 7 × 54y

⇒1 = 13x + 54y

⇒13 × 25 + 54 × (-6) = 13x + 54y

on comparing we get, x = 25 and y = -6

Therefore GCD (119, 378) = 7 and x = 25 and y = -6