### Example[edit]

The number 54 can be expressed as a product of two integers in several different ways:Thus the**divisors of 54**are:Similarly**the divisors of 24**are:The numbers that these two lists share in common are the**common divisors**of 54 and 24:The greatest of these is 6. That is the**greatest common divisor**of 54 and 24. One writes:### Using Euclid's algorithm

- ,

where

- .

If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:

- if
*a*>*b* - if
*b*>*a* **Code to find the Greatest Common Divisor of two numbers.**int GCD(int a,int b) { while(b^=a^=b^=a%=b); return a; }

`unsigned greatestCommonDivisor(unsigned m, unsigned n) { if(n == 0) return m; return greatestCommonDivisor(n, m % n); }`

- If we know the greatest common divisor (GCD) of integers a and b, we can calculate the LCM using the following formula.
LCM(a,b) = a × b GCD(a,b)

## Comments

## Post a Comment