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?
Tell me more
×
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.
|
|
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$. |
|||
|
|
