Question

Define gcd. Find gcd of 427 and 616 and express it in the form of 427x+616y.

Answer 1

greatest gcd=7..........

Answer 2

GCD:

GCD( greatest common divisor) of two or more numbers is the largest number that divides all the given numbers exactly . It is also known as highest common factor (HCF)


By Euclid Algorithm for 427 and 616

616= (1× 427)+189………(1)


Here r1 ≠0

427= (2×189) +49…………(2)

r2 ≠ 0

189= 3×49+ 42……………(3)

r3 ≠0

49= 1×42+ 7……………….(4)

r4 ≠0

42= 6×7 + 0……………….(5)

r5 = 0.

Hence, GCD of (427,616) is 7

GCD (427, 616) = 7

Now to express the GCD as a linear combination of the two given numbers start with equation 4 and successively eliminate the previous remainders.


7 = 49 + (−1)×42

[ From eq (4) ]

7 = 49 + (−1){189 + (−3)×49}

[ From eq (3) ]


7 =4× 49 − 189

7 =4× {427 + (−2)×189} − 189

[ From eq (2) ]

7 =4×427 + (−8)×189 − 189

7 =4×427 + 189(-8-1)

7 =4×427 + 189 (−9)

7 =4×427 + (−9){616 + (−1)427}

[ From eq (1) ]

7=4×427 + (−9)×616 + 9×427

7=4×427 + 9×427+ (−9)×616

7 = 427 ( 4+9) + (−9)×616


7 =13×427 + (−9)×616

Thus gcd(427, 616) = 7

7 = 427 x + 616 y,

where x = 13 and y = −9.

==================================================================
Hope this will help you...