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$

1 Answer 1

Reset to default
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
  • 1
    $\begingroup$ Good catch (that $360 = 19^2-1$). This makes generalization obvious. $\endgroup$
    – marty cohen
    Mar 22, 2017 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.