Pairs with a Great Divisor

$\sqrt{1000} = 31.62... < 32$ . From $2$ to $31$ , there are $11$ prime numbers.

Consider the set of composite numbers $\{2^2, 3^2, ..., 31^2\}$ , which are the square of the prime numbers less than or equal to 31. It is clear that the greatest common divisor of any 2 numbers is $1$ . This shows that we need $> 11$ numbers. [Note that this is not the only sequence of 11 numbers that would work. For example, $\{ 2^9, 3^6, 5^4, 7^3, 11^2, \ldots, 31^2\}$ will also work. - Calvin]

Conversely, if we are given any set of 12 composite numbers less than 1000. For $x$ a composite number, let $p_x$ be the smallest prime that divides $x$ . Since $x \leq 1000, p_x \leq \sqrt{1000}$ so $p_x \leq 31$ . There are $11$ possible values of $p_x : 2, 3, 5, 7, \ldots , 31$ . Since we have $12$ composite numbers from $1$ to $1000$ , by pigeonhole principle, there must be $2$ numbers which have the same value of $p_x$ Therefore, the greatest common divisor of that $2$ numbers is $p_x \neq 1$ [Not true. All we know is that the GCD of the 2 numbers is a multiple of $p_x$ , and hence not 1 - Calvin] So, the minimum value of $N$ is $12$ .

[Edits for clarity - Calvin]

$\sqrt{1000} < 32$ . The prime numbers up to 32 are $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ and $31$ . As such, if we pick any 12 composite numbers, they will have at least 12 primes, and hence 2 of them have a GCD that is greater than 1. Conversely, the 11 numbers $2^2$ , $3^2$ , $5^2$ , $7^2$ , $11^2$ , $13^2$ , $17^2$ , $19^2$ , $23^2$ , $29^2$ and $31^2$ all have pairwise GCD of 1. Hence, the minimal value of $N$ is $12$ .

THERE ARE 1000 NUMBERS AT ALL. we have to take such numbers which have different factors in other words squares of prime numbers as their factors did not match and then we take a number whose divisor is same to only one number in that set. 2 2=4, 3 3=9, 5 5=25, 7 7=49, 11 11=121, 13 13=169, 17 17=289, 19 19=361 , 23 23=529 , 29 29=841, 31*31=961 and thus we have 11 numbers in which no factors are same [ in other words greatest divisor is one]. Now we can take take any remaining number in the set but only once . For example, if we take the 12th number 4 then we take two numbers from the set 4 and 2 and hence the greatest divisor is 2 not 1. [make sure that you are not taking a prime number in the examples] HOPE YOU UNDERSTOOD.

The 168 primes from 1-1000 is misleading. Really what we need to find is the number of primes under $\sqrt{1000}$ since those numbers are the ones, when squared will all have a highest common divisor of 1. Under 33 there are 11 primes

2 3 5 7 11 13 17 19 23 29 31

However we need to add another to ensure that there are two with a greatest common divisor not 1.

N is the number of prime integers from (1 to X) + 1, where X is the previous highest integer of the square root 1000.

Hence, X=integer(sqrt(1000))=31

Thus, N is the number of primes (from 1 to 31 including 31) + 1 N=11+1=12

numbers can be broken down into products of prime numbers....so taking this into account the squares of prime numbers can only be divided by themselves, one and the prime number number they are squares of...thus the squares of prime numbers are composite yet co prime...thus by this fact the squares of prime numbers from 2 to 31, will all be co prime, which are eleven in number... therefore if we pick these 11 numbers and then any composite number then we end up with atleast two numbers which have a gcd other than 1

As we cannot pick prime numbers from the set, and must pick composite ones whose gcd with each other is 1, if we pick a number which is divisible by a prime p , then that prime may not be chosen again.

If we begin to construct such a solution we see that it is best to pick numbers that have the smallest possible number of different prime divisors, which is one since we can choose powers of prime numbers. The smallest power which makes the number composite is obviously 2. The biggest squared prime we can take from the sequence form 1 to 1000 is \sqrt{1000} \approx 31.

So the picked numbers are 4,9,25,49..., 961. There are 11 such numbers, and we see that we cannot form another number <=1000 using this method, but we can multiply the smaller numbers with some primes >31 so that we don't exceed 1000, which doesn't change the final result which is 11 .