Prove that any set of 46 distinct 2-digit numbers contains two distinct numbers which are relatively prime.

This is what I am trying to prove. I have a feeling that it would be using the pigeon hole principle but I just cannot figure it out. This is what I found interesting so far: There are 90 2-digits numbers ([10,99]), which means that there are exactly 45 even numbers, which means that in a set with 46 numbers, there must be at least one odd number. Though I do not know what to make of that... Also, 46 is optimal, in the snse that there exists a set of 45 distinct 2-digit numbers so that no two distinct numbers are relatively prime.


Suppose by contradiction that $S$ is a set of $46$ integers in $\{10, \ldots, 99\}$ such that no two distinct elements $a, b \in S$ are relatively prime; i.e., for all $a, b \in S$ such that $a \ne b$, $\gcd(a,b) > 1$.

A few key observations are needed. First is that if $b = a+1$, then $\gcd(a,b) = 1$. So $S$ cannot contain any consecutive elements. Second, what is the maximal size of the set $S$ under this condition? Since there are $99 - 10 + 1 = 90$ two-digit numbers, one can choose at most half, or $45$ of these numbers in such a way that there are no two consecutive elements. But this contradicts the assumption that $|S| = 46$; therefore, no such $S$ exists.

In short, the proof such a set doesn't exist merely relies on the fact that any two consecutive integers are relatively prime.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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