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?
-
$\begingroup$ can you give an example of such a set $S$? $\endgroup$– Ittay WeissJan 27, 2013 at 23:19
-
$\begingroup$ Such as (6,9,15), they are not relatively prime to each other. $\endgroup$– JinJan 27, 2013 at 23:20
-
$\begingroup$ 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. $\endgroup$– Asaf Karagila ♦Jan 27, 2013 at 23:20
-
$\begingroup$ Sorry, new user and had no idea what to tag the question with since I didn't find prime or coprime tags. $\endgroup$– JinJan 27, 2013 at 23:20
-
1$\begingroup$ It might be interesting to consider $S=\{pq,pr,qr\}$ for distinct primes $p,q,r$. $\endgroup$– Brian M. ScottJan 27, 2013 at 23:35
2 Answers
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$.