Use the Euclidean algorithm to find god390 72 and then expre

Use the Euclidean algorithm to find god(390, 72) and then express it as a linear combination of 390 and 72.

Solution

To find gcd(390,72) using Euclidean algorithm:

390 = 5 X 72 + 30

72 = 2 X 30 + 12

30 = 2 X 12 + 6

12 = 2 X 6

So,

gcd(390,72) = gcd(72,30)=gcd(30,12) = gcd(12,6) =6.

To express gdc(390,72) as a linear combination of 390 and 72:

i.e., to find integers x and y such that :

gcd(390,72)=x 390 + y 72.

We have:

6 = 30 - 2 X12

   = 30 - 2 X (72 - 2 X 30)

    = 5 X 30 - 2 X 72

6 = 5 X (390 - 5X 72) = 2 X 72 = 5 X 390 - 27 X 72.

6 = 5 X 390 - 27 X 72

= x 390 + y 72.

Thus,

gcd (390,72) = x 390 + y 72,

where,

gcd(390,72) = 6,

x = 5

y = - 27