Greatest common divisor

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

Algorithm

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}$