2
$\begingroup$

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.

  • 0
    I have got this far: gcd($a_1, \dots, a_n$) thus d|$a_i$, $i=1, \dots n$ and gcd($a_1, \dots, a_{n-2},gcd(a_{n-1}, a_n))$ thus d|$a_j$, $j=1, \dots, n-2$. How would you continue from this?2011-09-07

3 Answers 3

2

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.

1

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

0

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

Exercise 1.9 - Your claim.

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