# Prove at least two are not relatively prime, for any $8$ composite positive integers not exceeding $360$

Prove that in any $8$ composite positive integers not exceeding $360$, at least two are not relatively prime.

What I think is as below.

First we know there are $41$ prime numbers less than $180$, and that are all factors of $8$ composite integers, then try to find "least" $8$ composite integers then we can get a contradiction, but I do not know how to find these least $8$ composite integers.

$360$ is just $1$ less than $19^2$, so every number in $\{1,\ldots,360\}$ is either prime or divisible by a prime less than $19$, i.e. by one of $2,3,5,7,11,13,17.$ Just seven primes are here. Every one of your eight composite numbers is divisible by at least one of these seven. So use the pigeonhole principle.
• Good catch (that $360 = 19^2-1$). This makes generalization obvious. Mar 22, 2017 at 2:34
• $1$ is in $\{1,\ldots,360\}$ and in not prime nor divisible by a prime less than $19$. Jan 19 at 10:43