12
$\begingroup$

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.

$\endgroup$

1 Answer 1

22
$\begingroup$

$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.

$\endgroup$
2
  • 1
    $\begingroup$ Good catch (that $360 = 19^2-1$). This makes generalization obvious. $\endgroup$ Mar 22, 2017 at 2:34
  • $\begingroup$ $1$ is in $\{1,\ldots,360\}$ and in not prime nor divisible by a prime less than $19$. $\endgroup$
    – jjagmath
    Jan 19 at 10:43

You must log in to answer this question.

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