According to the Pigeonhole Principle, if we have p pigeonholes or boxes and q items to go in the boxes and if q>p (more items than pigeonholes), at least one pigeonhole (box) will contain more than one item.
There are 47 prime numbers between 1 and 200 (including 1):
(1, )2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.
Let P and C be the number of primes and composites, then P+C=101. If P=47 then C=54 (if all primes are selected then there must also be 54 composites). In this case, since two prime numbers have no common factors (other than 1), their lowest common factor is 1, so proving the proposition concerning m,n∈set of primes. The case is also proved if P>1, because there will be at least one pair of primes, which may or may not include the number 1.
If P=1 then C=100. This means there are 46 primes not selected, and the composites will consist of products of at least two of the remaining 24 primes. For example: if the selected prime is 2 then the 100 composites will contain some of the set { 4, 6, 8, ..., 198, 200 } which has 99 elements. But C=100 so, by the pigeonhole principle
The composites will be composed only of the primes between 2 and 97 (25 primes). If P=0 then C=101, and the composites can only include products of two or more of the 25 primes. But C=100, so that means, according to the Pigeonhole Principle, that we need one other composite composed of a different prime number to the one selected (i.e., 2) and another unselected prime. This implies that there are no common factors to at least one pair of numbers m and n, even if all the selected composites are multiples of 2.
If the selected prime was number 3, then the composites will contain 65 multiples of 3 and since C=100, we would need at least 35 composites which are not multiples of 3 to make up the numbers. Therefore there will be more examples of m and n satisfying the proposition.
