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
  • 1
    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
up vote 2 down vote accepted

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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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