(In Python): Write a function gcd(a, b) that returns the greatest common divisor of the parameters a and b.
You can use the Euclidean algorithm, which is based on the fact that gcd(a, b) = gcd(b mod a, a).
Say you want to find the gcd of 462 and 1071:
gcd(462, 1071) = gcd(1071 mod 462, 462) = gcd(147, 462)
gcd(147, 462) = gcd(462 mod 147, 147) = gcd(21, 147)
gcd(21, 147) = gcd(147 mod 21, 21) = gcd(0, 21)
gcd(0, 21) = 21, since the gcd of 0 and any positive integer x is just x itself
Hence, gcd(462, 1071) = 21. Note that it's not necessary to figure out which number is smaller for the algorithm to work:
gcd(1071, 462) = gcd(462 mod 1071, 1071) = gcd(462, 1071)