Wednesday, March 15, 2017

numerical methods - Greatest common divisor of more than two numbers

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 4.



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,[11] but it can also be calculated
by repeatedly taking the GCDs of pairs of numbers.[12] 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?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...