Euclid's Algorithm

The Greatest Common Divisor ( GCD ) of  two numbers is a number. The number ( GCD ) causes division of the two numbers. This number ( GCD ) is the greatest number that is possible. This divisor partially forms the two numbers. Adding  the divisor successively may result in formation of the two numbers.

One can note that when the divisor is the greatest, the division of the dividend is the sharpest. The division operation is very effective.

When the Greatest Common Divisor of two numbers is considered, we think of a number that can cause division of both the numbers. Here the two numbers are unequal. The Greatest Common Divisor causes divisions of the two numbers differently. This is clear from the two different quotient values. 

The GCD value is very interesting to note. It relates very well with the two numbers. The GCD of two even numbers is also an even number. The GCD of two odd numbers is an odd number. So, we can say that GCD is an abstraction of the two numbers in many ways. 

We can say that the GCD concept talks about mathematical connectivity. It stands to unite numbers in mathematical ways. It tells how maximal division of two numbers can be caused by a single number. 

_____________________________

Euclid's Algorithm:

This algorithm is used to calculate the

GCD of two numbers. 

Assumption: The first number is greater than the second. 

1 ) Input first number m

2 ) Input second number n

3) r = m % n

4 ) if r = 0

       Print n is GCD

       Goto Step ( 6 )

5 ) m = n

      n = r

      Goto Step ( 3 )

6 ) Stop

____________________________

Algorithm Tracing Activity l:

Pass I:-

1 ) m = 8

2 ) n = 4

3 ) r = m % n = 8 % 4 = 0

4 ) If r = 0 ( Yes )

       4 ( = n ) is the GCD

       Goto Step ( 6 )

6 ) Stop 

___________________________

___________________________

Algorithm Tracing Activity ll:

Pass I:

1 ) m = 18

2 ) n = 12

3 ) r = m % n = 18 % 12 = 6

4 ) r = 0 ( No )

5 ) m = n 

     Hence m = 12

     n = r

     Hence n = 6

     Goto Step ( 3 )

#########

For Pass II 

 ( Valid Intermediate Values ):

       m = 12

       n = 6

#########

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Pass II:

( 3 ) r = m % n 

          =  12 % 6 ( From Pass I )

          = 0

( 4 ) if r = 0 ( Yes )

         Print 6 ( = n ) is GCD

         Goto Step ( 6 )

( 6 ) Stop

_____________________________