Proof of gcd of a list of numbers

Question

Prove that gcd of a list of numbers say gcd(a, b, c, d) = gcd(a, gcd( b, c, d)). I know that the above-stated method of finding gcd of a list of numbers works. but I am not able to prove it. Can someone help with this?

Answer 1

Hint: For $a_1,\dots,a_n \in \mathbb Z$, let $D(a_1,\dots,a_n) = \{ d \in \mathbb N : d \mid a_1, \dots, d \mid a_n \}$. Then by definition $\gcd(a_1,\dots,a_n) = \max D(a_1,\dots,a_n)$. Note that $D(a_1,\dots,a_n) = D(a_1) \cap \dots \cap D(a_n)$ and use associativity of set intersection.

Answer 2

Since gcd(a,b,c,d) devides b,c and d this means also that gcd(a,b,c,d) devides gcd(b,c,d) and therefore (with gcd(a,b,c,d) devides a) that gcd(a,b,c,d) devides gcd(a, gcd( b, c, d)).

On the other hand gcd(a, gcd(b,c,d)) devides b because gcd(a, gcd(b,c,d)) devides gcd(b,c,d) which devides b.

Therefore gcd(a, gcd(b,c,d)) devides a, b, c and d. So it must also devide gcd(a,b,c,d).

So you have gcd(a,b,c,d) divides gcd(a, gcd(b,c,d)) and vice versa, so they must be equal due to the partial ordering defined by divisibility.