Homework gcd. Show that $\gcd(a_1,a_2,a_3,...a_k) = \gcd(\gcd(a_1,a_2),a_3,...a_k)$

Question

Help me with this please show that $\gcd(a_1,a_2,a_3,...a_k) = \gcd(\gcd(a_1,a_2),a_3,...a_k)$

How can I start?

Answer 1

You could try to separate it into two different problems:

(1) prove that $\gcd(a_1,a_2,...,a_k) \mid \gcd(\gcd(a_1,a_2),a_3,...,a_k)$.

(2) prove that $\gcd(\gcd(a_1,a_2),a_3,...,a_k) \mid \gcd(a_1,a_2,...,a_k).$

Is one of those directions trivial? If so, why? You could also try to prove these by contradiction.

Also, how much do you know about prime facorization? How the $gcd$ can be expressed in term of prime factors? If so, it might also be worth a try to go about it that way.

Answer 2

You may assume that $k=3$. Then we need to show that $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$. We will show that $\gcd(\gcd(a, b), c)$ satisfies the definition for $\gcd(a, b, c)$:

1.) We know that $\gcd(\gcd(a, b), c)\mid gcd(a, b)$ and $\gcd(\gcd(a, b), c) \mid c$. Moreover, $\gcd(a, b) \mid a$ and $\gcd(a, b) \mid b$, so $\gcd(\gcd(a, b), c) \mid a$ and $\gcd(\gcd(a, b), c)\mid b$.

2.) Suppose $d′$ is a positive integer such that $d′\mid a$, $d′\mid b$ and $d′\mid c$. Then by the Euclidean algorithm we know that $d′\mid\gcd(a, b)$ and so, by definition, $d′ ≤ \gcd(\gcd(a, b), c)$.