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.

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.

share|improve this question
3  
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
3  
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
5  
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

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

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.