# How is following possible: $\gcd(a_{n-1}, a_n) \mid a_{n-1}$ and $\gcd(a_{n-1}, a_n) \mid a_n$?

Following is extract from the proof that proves following: Let $a_1,\dots, a_n$, such that $a_{i_0} \neq 0$. Show that $\gcd(a_1,\dots, a_n)=\gcd(a_1,\dots, a_{n-2},\gcd(a_{n-1},a_n))$(hint! Show that left side and right side sets $A_1$ and $A_2$ of common factors are the same. So basically $A_1 \subset A_2$ and $A_2 \subset A_1$.

If $k \in A_2$, then $k \mid a_i$ $\forall i=1, \dots, n-2$ and $k \mid \gcd(a_{n-1}, a_n)$. Secondly $\gcd(a_{n-1}, a_n) \mid a_{n-1}$ and $\gcd(a_{n-1}, a_n) \mid a_n$ so by transitivity $k\mid a_{n-1}$ and $k \mid a_n$. Therefore $k \in A_1$ in other words $A_2 \subset A_1$? How is following possible: $\gcd(a_{n-1}, a_n) \mid a_{n-1}$ and $\gcd(a_{n-1}, a_n) \mid a_n$? Would someone unravel the reasons that one can claim following to be true?

-
I'm not sure I understand your question. $\gcd(a_{n-1},a_n)$ is the greatest common divisor, so of course it divides $a_{n-1}$ and $a_n$. That's the definition of divisor. –  AMPerrine Oct 28 '11 at 15:28
In general, $gcd(a,b)\mid a$ and $gcd(a,b)\mid b$. That's because $gcd(a,b)$ is a common divisor of $a$ and $b$. This proof is just using $a=a_{n-1}$ and $b=a_n$ –  Thomas Andrews Oct 28 '11 at 15:45

Forget about the entire rest of the problem; given any two integers $x$ and $y$, $$\gcd(x,y)\mid x\quad\text{ and }\quad \gcd(x,y)\mid y.$$ The definition of $\gcd(x,y)$ is that it is the greatest integer having this property (hence the name, greatest common divisor).
Then, let $x=a_{n-1}$ and $y=a_n$.