# Prove that any set of integers that are relatively prime in pairs are relatively prime

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?

• 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$. – Git Gud Jun 18 '14 at 0:41
• 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)$. – Stefan Mesken Jun 18 '14 at 0:43
• What if $n=1$ and $a_1\gt1$? – bof Jun 18 '14 at 2:47

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$.
• So i was right there...I just needed $a_1$ and $a_2$. Awesome! – Lalaloopsy Jun 18 '14 at 0:41
• The assumption "$n\ge2$" was not stated in the question. – bof Jun 18 '14 at 2:45
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.