SICP had a very concise solution (Euclidean Algorithm)
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b))))