Suppose I have a set of $n$ numbers and their gcd is $d$. If I divide every number by $d$, is it possible to find a pair that is relatively prime? Intuitively yes, but how do I prove it? I tried proceeding by contradiction, like what happens when there are no two numbers who don't share a divisor.


1 Answer 1


You can't prove this because it's not true. Consider


The $\gcd$ of all of them is $1$, but there is no pair whose $\gcd$ is $1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .