# show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$

Let $a_1, \dots, a_n \in \mathbb Z$ such that $a_{i_0} \neq 0$ for some $i_0 \in \{1, \dots, n\}$. How to show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$. (Hint: show that the sets of the common factors of the left and right side are the same).

Question is Exercise 1.9 on pp252 in Elementary Number Theory by Gareth Jones.

-
This is extremely straightforward. What have you tried? –  Brian M. Scott Sep 7 '11 at 7:26
I have got following. gcd($a_1, \dots, a_n$) = gcd($a_1, \dots, a_{n-2}$,gcd($a_{n-1},a_n$)) <=> $x_1a_1+ \dots + x_na_n = x_1a_1 + \dots + x_{n-2} a_{n-2} + x_{n-1}(x_{n-1}a_{n-1}+x_na_n)$ <=> ? –  laovultai Sep 7 '11 at 7:35
What do you think about the hint? –  anon Sep 7 '11 at 7:41
I don't know how to show that they have same sets. –  laovultai Sep 7 '11 at 7:52
I’d say that you’re on the wrong track altogether and need to start over. You need to show that every common divisor of $a_1,\dots,a_n$ is also a common divisor of $a_1,\dots,a_{n-2},\operatorname{gcd}(a_{n-1},a_n)$ and vice versa. Start with some $d$ that divides each of $a_1$ through $a_n$ and show that it divides each number in the second list; then start with some $d$ that divides every number in the second list and show that it divides each of the $a_i$. –  Brian M. Scott Sep 7 '11 at 7:58

I don’t want to be rude or overly discouraging, but I’m not sure that you’re ready for this material: what you wrote in that last comment doesn’t make a whole lot of sense. Let’s try this: I’ll take you through half of the argument in detail and give you a chance to use that as a model for the second half.

You want to show that $\gcd(a_1,\dots,a_n) = \gcd(a_1,\dots,a_{n-2},\gcd(a_{n-1},a_n))$; one way to do this is to show that every common divisor of $a_1,\dots,a_n$ is also a common divisor of $a_1,\dots,a_{n-2}$ and $\gcd(a_{n-1},a_n)$. In other words, you want to show that the set of common divisors of $a_1,\dots,a_{n-1}$, and $a_n$ is equal to the set of common divisors of $a_1,\dots,a_{n-2}$ and $\gcd(a_{n-1},a_n)$. One very common way to show that two sets are equal is to show that every member of the first set is a member of the second, and vice versa. I’ll show that every common divisor of $a_1,\dots,a_{n-1}$, and $a_n$ is a common divisor of $a_1,\dots,a_{n-2}$ and $\gcd(a_{n-1},a_n)$ and leave you to show that every common divisor of $a_1,\dots,a_{n-2}$ and $\gcd(a_{n-1},a_n)$ is a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$.

Suppose that $d$ is a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$. This means that $d \mid a_1,d \mid a_2,\dots,$ $d\mid a_{n-1}$, and $d\mid a_n$. To show that $d$ is a common divisor of $a_1,\dots,a_{n-1}$ and $\gcd(a_{n-1},a_n)$, we must show that $d\mid a_1,d\mid a_2,\dots,d\mid a_{n-2}$, and $d\mid \gcd(a_{n-1},a_n)$. By hypothesis $d \mid a_1,d \mid a_2,\dots,$ $d\mid a_{n-2}$, so we really only have to show that $d\mid\gcd(a_{n-1},a_n)$.

For brevity let $\delta = \gcd(a_{n-1},a_n)$; then $\delta\mid a_{n-1}$ and $\delta\mid a_n$. But that’s true of any common divisor of $a_{n-1}$ and $a_n$, and $\delta$ isn’t just any old common divisor of these two numbers: it’s the greatest common divisor. This implies that every common divisor of $a_{n-1}$ and $a_n$ is a divisor of $\delta$: this is an important property of the greatest common divisor that gets used over and over. In particular, $d\mid\delta$, since $d$ is a common divisor of $a_{n-1}$ and $a_n$. And that’s exactly what we needed: we’ve now shown that if $d$ is a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$, then it’s also a common divisor of $a_1,\dots,a_{n-1}$ and $\gcd(a_{n-1},a_n)$.

Now see if you can manage the opposite direction: if $d$ is a common divisor of $a_1,\dots,a_{n-1}$ and $\gcd(a_{n-1},a_n)$, then $d$ is also a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$. If anything, it’s a little easier.

-

Origin - Elementary Number Theory, Jones, p9, Exercises 1.8 and 1.9

I refashion Brian M. Scott's answer in Jones's way.

Exercise 1.8 - c|a and c|b $\iff c|\gcd(a,b)$

Proof of Forward Direction - Postulate that $d$ is a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$. This means that $d \mid a_1,d \mid a_2,\dots,$ $\color{brown}{d\mid a_{n-1}, and \; d\mid a_n}$. To show that $d$ is a common divisor of $a_1,\dots,a_{n-1}$ and $\gcd(a_{n-1},a_n)$, we must show that $d\mid a_1,d\mid a_2,\dots,d\mid a_{n-2}$, and $d\mid \gcd(a_{n-1},a_n)$. By hypothesis $d \mid a_1,d \mid a_2,\dots,$ $d\mid a_{n-2}$, so we really only have to show that $d\mid\gcd(a_{n-1},a_n)$.

But by cause of the forward direction of Exercise 1.8, $\color{brown}{d\mid a_{n-1}, and \; d\mid a_n} \implies d|\gcd(a_{n - 1}, a_n)$.

Proof of Backward Direction - Postulate that $d$ is a common divisor of $a_1,\dots,a_{n-2}$ and $\color{seagreen}{\gcd(a_{n-1},a_n)}$. I want to prove $d$ is also a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$. The only difference is to prove $\color{brown}{d\mid a_{n-1}, and \; d\mid a_n}$.

By cause of the backward direction of Exercise 1.8, $d|\color{seagreen}{\gcd(a_{n - 1}, a_n)} \implies \color{brown}{d\mid a_{n-1}, and \; d\mid a_n}$. Then $d$ is also a common divisor of $a_1,\dots,a_{n-1}$, and $a_n$.

-

HINT $\rm\quad d\ |\ a,b,c,c' \iff\ d\ |\ a,b,\ d\ |\ c,c' \iff\ d\ |\ a,b,(c,c') \iff\ d\ |\ (a,b,(c,c'))$

NOTE $\$ It boils down to associativity of $\wedge\:$ ("and"), where $\rm\ d\ |\ a,b,c\ :=\ d\:|\:a \wedge (d\:|\:b \wedge d\:|\:c)$

-