3
$\begingroup$

It seems pretty obvious, but how to prove?

I thought that maybe the way to go was by contradiction. So suppose that a set of integers is not relatively prime but pairs of members are coprime. We know for the set $$S=\{a_1,a_2,a_3,...,a_{n-1},a_n\}$$ $(a_i,a_j)=1, \forall i,j, i\neq j$ If the set of integers was not coprime, then $$(a_1,a_2,a_3,...,a_{n-1},a_n)=k$$ for some integer $k$. By the definition of the greatest common divisor, we know that $$k|a_i, \forall a_i\in S$$ However, for all pairs $a_i, a_j$, the only number that divides each is $1$ since $(a_i,a_j)=1$ Thus, no members of $S$ have a common divisor of $k$ which is a contradition. Therefore, the set of integers that are relatively prime in pairs is also relatively prime

Is this logical? I know there is a theorem that states $(a_1,a_2,...a_{n-1},a_n)=((a_1,a_2,...,a_{n-1}),a_n)$ which might help the cause, but that exercise has not been crossed yet in my textbook, and I think that the linear fashion of the text should be upheld... Thoughts?

$\endgroup$
3
  • 2
    $\begingroup$ At this level of elementary-hood I would expect to see "$\ldots$" replaced by induction. Otherwise it's good. But there's not need to assume they are not co-prime. Just take $k$ as you did and conclude $k=1$. $\endgroup$
    – Git Gud
    Jun 18, 2014 at 0:41
  • 1
    $\begingroup$ Your proof is correct. Another way to see this, is to note that in the principal ideal domain $\Bbb Z$ the ideal $(a,b)$ is generated by the $gcd(a,b)$. So if $(a,b) = \Bbb Z$, i.e. $gcd(a,b) = 1$, then $(a,b,c) = \Bbb Z$ for every $c \in \Bbb Z$. So in fact, we only need $(a,b) = 1$ for two elements in $S$ rather then for every pair $(a,b)$. $\endgroup$
    – Stefan Mesken
    Jun 18, 2014 at 0:43
  • $\begingroup$ What if $n=1$ and $a_1\gt1$? $\endgroup$
    – bof
    Jun 18, 2014 at 2:47

2 Answers 2

Reset to default
6
$\begingroup$

Pretty much as you have said. To put it more concisely, . . .

Let $d$ be a positive common factor of $a_1,\ldots,a_n$. Then $d$ is a common factor of $a_1,a_2$. Since by assumption the numbers are relatively prime in pairs, $d$ can only be $1$.

$\endgroup$
2
  • $\begingroup$ So i was right there...I just needed $a_1$ and $a_2$. Awesome! $\endgroup$
    – Lalaloopsy
    Jun 18, 2014 at 0:41
  • 1
    $\begingroup$ The assumption "$n\ge2$" was not stated in the question. $\endgroup$
    – bof
    Jun 18, 2014 at 2:45
3
$\begingroup$

Hint $ $ For sets of naturals, the property of having a nontrivial common divisor descends to subsets, therefore, the negation of the property, having no nontrivial common divisor, ascends to supersets.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .