10
$\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$
20
$\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$
  • 1
    $\begingroup$ Good catch (that $360 = 19^2-1$). This makes generalization obvious. $\endgroup$ – marty cohen Mar 22 '17 at 2:34

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.