Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

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

share|improve this answer

Sometimes. Consider $S = \{15,21,35\}$. Each pair has a factor in common but $15+21=36$ is relatively prime to $35$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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