How to show that gcd of n numbers can be expressed as their linear combination. For positive integers $a_1, a_2, ..., a_n$, prove there exists integers $k_1, k_2, ..., k_n$ such that $$gcd(a_1, a_2, ..., a_n)=k_1a_1+ k_2a_2+ ...+k_n a_n$$
I know the case for $n=2$ but have no idea how to approach this.
Any hint will be appreciated.
 A: First, we prove a lemma as @user251257 mentioned: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$. Let $p = \gcd(a, b)$ and $q = \gcd(p, c)$. We know $q \mid c, p$ and also $p \mid a, b$, so together $q \mid a, b, c$. If any other number $d \mid a, b, c$, then $p \mid d$ by its definition as $\gcd(a, b)$. But $q \mid p$ so $q \mid d$ and hence $q = \gcd(a, b, c)$.
Note that this lemma can be recursively applied to get $\gcd(a_1, a_2, \dotsc, a_n) = \gcd(\gcd(a_1, a_2, \dotsc, a_{n-1}), a_n)$.
Now we will prove the original statement by induction over $n$. You say that you know it is true for $n = 2$, so I will not prove it here. The induction hypothesis is that $\gcd(a_1, a_2, \dotsc, a_{n-1})$ is expressible as a linear combination of the $a_i$. Then $\gcd(a_1, a_2, \dotsc, a_n) = \gcd(\gcd(a_1, a_2, \dotsc, a_{n-1}), a_n)$ which is the greatest common divisor of some linear combination of the $a_i$ where $i < n$, and $a_n$. From the $n = 2$ case this is again a linear combination and we are done. (Linear combination of a linear combination is still a linear combination.)
