# Construct relatively prime pairs from set of nonrelatively prime numbers

Is it possible? Given a set of numbers S such that every possible combination of the numbers in S are nonrelatively prime, can you construct a pair of relatively prime numbers by adding up arbitrary combinations of the numbers from S?

• can you give an example of such a set $S$? – Ittay Weiss Jan 27 '13 at 23:19
• Such as (6,9,15), they are not relatively prime to each other. – Jin Jan 27 '13 at 23:20
• Ah, of course! Sets, it must be set theory! Coincidentally this argument never goes through to [number-theory], although in this case it's much closer to number theory than it is to set theory. – Asaf Karagila Jan 27 '13 at 23:20
• Sorry, new user and had no idea what to tag the question with since I didn't find prime or coprime tags. – Jin Jan 27 '13 at 23:20
• It might be interesting to consider $S=\{pq,pr,qr\}$ for distinct primes $p,q,r$. – Brian M. Scott Jan 27 '13 at 23:35

If there is a number $d\gt1$ that divides every element of $S$, then it is easy to see that it will also divide every sum of elements of $S$, so, in this case, the answer is no.
If there is no such number $d$, then it is always possible to find two coprime integer linear combinations of elements of $S$. I'll show you a way to do it if $S$ has $3$ numbers, $S=\{{a,b,c\}}$, and you can think about how to generalize.
Let $t$ be the product of all the primes that divide $c$ but not $a$. Then $\gcd(a+bt,c)=1$. For, let $p$ be a prime dividing $c$. If $p$ divides $a$, then it can't divide $b$, nor $t$, nor $bt$, nor $a+bt$. If $p$ doesn't divide $a$, then it must divide $t$, so it divides $bt$, so it doesn't divide $a+bt$.
Sometimes. Consider $S = \{15,21,35\}$. Each pair has a factor in common but $15+21=36$ is relatively prime to $35$.