I'm coming from a programming aspect of this issue. So in Scheme code
(define (gcd a b) (if (= b 0) a (gcd b (modulo a b))))
works and uses recursion, i.e., the
...(gcd b (modulo a b)))) recursively calls the function
gcd again (and again) until the condition
b = 0 is met, to give the answer
a. So to use this function
(gcd 12 20) gives
Now, if I do this for more than two numbers, say $2, 12, 20, 120$
(gcd 2 (gcd 21 (gcd (20 120))))
I get the right answer too, i.e.,
2. Can someone tell me why this is working correctly from a math standpoint?
On Wikipedia's Euclidean Algorithm article, it says
The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example,
gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)
I'm guessing it has something to do with the commutable "product of all prime factors." But still, this is recursion inside of recursion pair-wise. Why does this work?