Question

Show the steps involved in calculating GCD(2095,200) using Euclidian algorithm.

Answer 1

Calculate the GCD(2095,200) using Euclidian algorithm:

Steps of Euclidian algorithm:

Finding the of GCD(X, Y):

Step 1: If X = 0 then GCD(X, Y) = Y

Step 2: If Y = 0 then GCD(X, Y) = X

Step 3: Write X as X = Y * Q + R quotient remainder form.

Step 4: Find the GCD(Y,R) repeating the above steps as GCD(X, Y) = GCD(Y,R)

Calculating GCD(2095,200) using Euclidian algorithm:

2095 = 200 * 10 + 95 (2095 ÷ 200 = 10 Quotient with Reminder R = 95)

200 = 95 * 2 + 10 (200 ÷ 95 = 2 Quotient with Reminder R = 10)

95 = 10 * 9 + 5 (95 ÷ 10 = 9 Quotient with Reminder R = 5)

10 = 5 * 2 + 0 (10 ÷ 5 = 2 Quotient with Reminder R = 0)

• When remainder R = 0 then the GCD is the divisor, Y, in the equation form X = Y * Q + R

• Here, in the above last equation. When R = 0, Y = 5. So, GCD = 5

GCD(2095,200) = 5

Description:

• GCD of 2095 and 200

X ≠ 0

Y ≠ 0

2095 ÷ 200 = 10 with R = 95. (Quotient Remainder form: 2095 = 200 * 10 + 95)

Find the GCD(200, 95) as GCD(2095, 200) = GCD(200, 95)

• GCD of 200 and 95

X ≠ 0

Y ≠ 0

200÷ 95= 2 with R = 10. (Quotient Remainder form: 200 = 95 * 2 + 10)

Find the GCD(95, 10) as GCD(200, 95) = GCD(95, 10)

• GCD of 95 and 10

X ≠ 0

Y ≠ 0

95 ÷ 10= 9 with R = 5. (Quotient Remainder form: 95 = 10 * 9 + 5)

Find the GCD(10,5) as GCD(95, 10) = GCD(10,5)

• GCD of 10 and 5

X ≠ 0

Y ≠ 0

10 ÷ 5 = 2 with R = 0. (Quotient Remainder form: 10 = 5 * 2 + 0)

When R = 0 then GCD = Y. So, GCD(2095, 200) = 5.