Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

up vote 8 down vote accepted

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$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.