gcd (greatest common divisor); O(log N)

int gcd(int a, int b)
{
    if (b==0) return a;
    return gcd(b, a%b);
}