Greatest common divisor of more than two numbers

Question

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?

Answer 1

Essentially it does not matter how you do group and associate the numbers, as long as all the numbers come into play at some time.

It works because you can see the GCD as two separate processes, done in sequence.

In the first one you are looking for the prime numbers that divide all the numbers. The order or the grouping are irrelevant because you are looking for a global property, and if two numbers are divisible by, say, $3$ and $7$, you can replace them by $3\cdot 7$ and no information is lost.

In the second phase, if there are prime numbers that are in the factorization of all the numbers, you are looking for the minimum of the exponents.

So, if $2$ numbers are divisible by $7^6$ and $2$ are divisible by $7^4$ and one by $7^2$, your GCD will contain the factor $7^{\min(6,4,2)}=7^2$.

I think it is intuitive to realize that to compute the minimum among several numbers you can group them as you want.

Answer 2

Cosndier the fact that for any three integers $u,v,w$, we have $$\min \{u,v,w\} = \min \{\min\{u,v\},w\} = \min \{u,\min\{v,w\}\} = \min \{\min\{u,w\},v\}.$$ We devise factorizations of $a, b, c$: $$a = p_1^{u_1} \cdots p_n^{u_n}$$ $$ b = p_1^{v_1} \cdots p_n^{v_n}$$ $$c = p_1^{w_1} \cdots p_n^{w_n} $$ for prime numbers $p_1,...,p_n$ (chosen so that each $p_i$ divides one of the numbers $a,b,c$) and for non-negative integers $u_i,v_i,w_i$ (which may be zero).

We then have $$\textsf{gcd}(a,b,c) = p_1 ^{\min\{u_1,v_1,w_1\}}\cdots p_n ^{\min\{u_n,v_n,w_n\}}$$ and, for example, $$\textsf{gcd}(a,b) = p_1 ^{\min\{u_1,v_1\}}\cdots p_n ^{\min\{u_n,v_n\}}.$$ Proving your desired statement becomes very easy from here!

Answer 3

From GCD in Wolfram you can compute the GCD starting from the factorization of each term:

$$t_i=\prod_{j=1..n}p_j^{\alpha_{i,j}}$$

where $p_j$ is the j-th prime number, $p_n$ is the maximum prime number in the factorization of all terms $t_i$ and $\alpha$ coefficients are non-negative integers (including 0).

The greatest common divisor of all terms is then found as:

$$GCD(t_1,t_2,...,t_N) = \prod_{j=1..n}p_j^{min(\alpha_{1,j},\alpha_{2,j},...,\alpha_{N,j})}$$

Hence, your problem has been reduced to computing the minimum function over n different sequences composed of N terms each.

Applying the algorithm to successive pairs is just the same as using the common iterative algorithm for finding the minimum over a sequence of numbers, for all the n sequences in parallel.