Euclidean Algorithm — GCD in O(log min(a,b))

Recursive

long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

Iterative

long gcd(long a, long b) {
  while (b != 0) { long t = b; b = a % b; a = t; }
  return a;
}

Complexity

O(log min(a, b)). Worst case: consecutive Fibonacci numbers.

Applications

Reducing fractions. Modular arithmetic. Cryptography. LCM = a·b/gcd.