Euclid's Algorithm For Finding Greatest Common Divisor

               What will you do if you want to find out Greatest Common Divider ( the largest positive integer which divides two or more integers without any remainder is called Highest Common Factor or Greatest Common Divisor)? Wel, there is a simple/general method to find out GCD of any numbers.

General Method

                Let’s assume two numbers as 16 and 24. For finding GCD first step is to find all the divisors of both numbers.

                Divisors (16) = { 2 , 4 , 8 }

                Divisors (24) = { 2 , 4 , 8 , 12}

                                Now we can point out GCD by observing the sets of both number’s divisors. For this case 8 is the largest divisor of both numbers.

                GCD (16,24) = 8

                GCD of any numbers cannot be greater than Smallest number in the Input set. So Implementation in Programming Language we can set loop for the smallest number of Input Data and find GCD of any numbers. Here is the function to find GCD using this method in  C/C++ language.

Euclid’s Algorithm

                Greek mathematician Euclid proposes very efficient method for finding GCD of two numbers. For Larger Number general method is not as efficient as Euclid.

                The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 20 & 30 has same GCD as 20 & 10 because 30 is replaced by the difference between 30 and 20 which is 10. If we continue this process, we eventually find GCD.

                GCD ( 20 , 30 ) = GCD ( 20 , 10 ) { 30 is replaced with (30-20) }

                                       = GCD ( 10 , 10 ) {20 is replaced with (20-10) }

                                    = 10 Because Both are same and every number is divisible by itself.

                We can implement in the programming language with difference OR we can do it with taking the modulo of numbers.

    Example Of Modulo Method to Find GCD

                For GCD ( 48 , 32) = GCD ( 32  , 16 ) because 48 is replaced with (48 mod 32) as Euclid suggest the difference of smaller number doesn’t impact on GCD.

                GCD (48 , 32 ) = GCD ( 32 , 16 )

                                      = GCD ( 16 , 0 )

                                      = 16 because GCD of any number with 0 is Number itself.

                Here is Implementation of Euclid’s Algorithm in C/ C++ language.