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$
  • 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 '14 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 '14 at 0:43
  • $\begingroup$ What if $n=1$ and $a_1\gt1$? $\endgroup$ – bof Jun 18 '14 at 2:47
4
$\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$
  • $\begingroup$ So i was right there...I just needed $a_1$ and $a_2$. Awesome! $\endgroup$ – Lalaloopsy Jun 18 '14 at 0:41
  • 1
    $\begingroup$ The assumption "$n\ge2$" was not stated in the question. $\endgroup$ – bof Jun 18 '14 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.