Finding GCD Using Euclidean Algorithm Proof

In this class, We discuss Finding GCD Using Euclidean Algorithm Proof.

The reader should have prior knowledge of the basics of GCD using the Euclidean algorithm. Click Here.

Before we move on to the mathematical proof, we refresh the concept of Euclidean procedure.

Take the numbers 36, 28.

We take the highest and divide with the least number.

In the next round, we take the reminder and the previous least number and divide.

The process is repeated till we get reminder zero.

Take the numbers a and b.

The numbers a and b are written as a = bq + r, where q is the quotient and r is a reminder.

Now, we take the remainder and the previous least value.

Second Round: We take b, r.

b, r is written as b = rq1 + r2

Next round, we take r, r1.

The elements r, r1 is written as r = r1q2 + r2.

The process is repeated till we have reminder zero.

a = bq + r we write GCD(a, b) = GCD(b, r)

b = rq1 + r1 we write GCD(b, r) = GCD(r, r1)

r = r1q2 + r2 we write GCD(r, r1) = GCD(r1, r2)

The above process is repeated till the remainder is zero.

GCD(x, 0) is x.