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?
Asked
Active
Viewed 285 times
1
-
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
-
[prime-numbers]? – Asaf Karagila Jan 27 '13 at 23:21
-
Ah, missed that somehow. Thanks! – Jin Jan 27 '13 at 23:21
-
@Jin, make your life slightly easier then and consider the set {3,6}. Can you construct relatively prime numbers by adding things up from this set? – Ittay Weiss Jan 27 '13 at 23:22
-
My intuition tells me no, but I can't think of a formal way to generalize the fact to all sets that satisfy the condition. – Jin Jan 27 '13 at 23:23
-
any number which is obtained by adding things from {3,6} must be of the form 3m+6k. This is a multiple of 3. – Ittay Weiss Jan 27 '13 at 23:23
-
1It might be interesting to consider $S={pq,pr,qr}$ for distinct primes $p,q,r$. – Brian M. Scott Jan 27 '13 at 23:35
2 Answers
2
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$.
Gerry Myerson
- 179,216
1
Sometimes. Consider $S = \{15,21,35\}$. Each pair has a factor in common but $15+21=36$ is relatively prime to $35$.
Dan Brumleve
- 17,796