Find GCD Using Euclidean Algorithm

In this class, we discuss Finding GCD using Euclidean algorithms.

The reader can take complete discrete mathematics and graph theory courses. Click Here.

First, we understand GCD using the factorial method.

In our Intermediate, we have found GCD using the factorial method.

Take the numbers, and using division, we find GCD.

Euclidean found a new way to identify the GCD of the numbers.

Example:

Find the GCD of the numbers 36 and 28.

First, divide the biggest number with the smallest number.

28 ) 36(

The reminder value is 8.

Now we consider 8 and 28 (the previous least value and the reminder)

Again do division

8) 28 (

The reminder value is 4.

We consider 4 and 8 (the previous least value and the reminder)

Again, do division.

4 ) 8 (

The remainder is zero.

The values are 4 and 0.

The GCD of 36, 28 is 4.

The division process is repeated until the remainder is zero.

Example:

Find the GCD of the numbers 36, 28, 14.

First, find the GD of the two numbers using the Euclidean algorithm.

GCD(36, 28 ) is 4.

Now find GCD of 14, 4.

The GCD of 14, 4 is 2.