Skip to main content
I have two numbers and I want to find the greatest common divisor (GCD) for them. Then, I have to find all the factors of two numbers and select "the common big one" from both the set of factors. It will be a tedious task for very big numbers.
There is a sleek procedure(algorithm) to do this . This algorithm is devised by euclid in 300 B.C. Let us find out GCD for 30 and 18 in euclid's way.
Divide the big integer by the small integer and get the remainder. 30 MOD 18 = 12.
Now divide the divisor 18 by the remainder 12 and get the new remainder. 18 MOD 12 = 6.
Next again, divide the divisor 12 by the remainder 6 and get the fresh remainder. 12 MOD 6 = 0
6 must be the GCD of 30 and 18 because it is derived from both the integers by repeated division and finally it divides perfectly without any remainder.
Verifying: 30 MOD 6 = 0 18 MOD 6 = 0
This is the good example for a computer algorithm. This simple algorithm can find GCD of any two large integers.
