Greatest common divisor

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The greatest common divisor (gcd) or Highest common factor ( HCF )of two integers is the greatest (largest) number that divides both of the integers evenly. Euclid came up with the idea of GCDs.

Algorithm[change | change source]

The GCD of any two positive integers can be defined as a recursive function: 
gcd(u,  v) = 
\begin{cases}
    gcd(v, u\mbox{ mod }v), & \mbox{if }v > 0 \\
    u,                          & \mbox{if }v = 0
\end{cases}

Examples[change | change source]

The GCD of 20 and 12 is 4, since 4 times 5 equals 20 and 4 times 3 equals 12. You can notice 3 and 5 have no common factor, hence their GCD is 1.

The GCD of 81 and 21 is 3.