Euclid's Algorithm

The greatest common divisor gcd of two numbers is the largest number that divides exactly into both of them. e.g. gcd(3,4)=1 and gcd(12,8)=4. Read http://en.wikipedia.org/wiki/Euclidean_algorithm.