Find the least positive integer $n$ such that any set of $n$ pairwise relatively prime integers greater than $1$ and less than $2005$ contains at least one prime number.

My solution: Let's reformulate our problem: Find the biggest $n_0\in \mathbb{N}$ such that exists the set of $n_0$ pairwise relatively prime integers $>1$ and $<2005$ contains no prime numbers. If we find that number $n_0$ then the number $n=n_0+1$ is answer to our initial stated problem.

Since $k=\pi(2005)=304$ where $\pi(x)$ - the number of prime less than $x$. Let's consider the set $A=\{p_1^2, p_2^2, \dots, p_{k}^2\}$ and it is obvious that this set consists of relatively prime numbers and does not containt prime number. But if we add one more number, namely $q$ from interval $(1,2005)$ then this $q$ will imply the following: $\text{gcd}(q, p_j)=p_j>1$.

Hence the biggest number is $n=304+1=305$.

However, the answer in the book is 15.

What is wrong with my reasoning?

EDIT: Let's take the set $A=\{p_1^2,p_2^2, \dots, p_{14}^2\}$ where $p_{14}=43$ and wee see that this set has relatively prime integers $>1$ and $<2005$ and contains no prime number. Hence $n_0\geqslant 14$. Let's take the set of $15$ numbers $\{a_1, a_2, \dots, a_{15}\}$ and let $q_i$ the least prime factor of $a_i$ and it's easy to see that sequence $\{q_1, q_2, \dots, q_{15}\}$ is pairwise distinct. Also $\hat{q}=\max q_{i} \geqslant p_{15}=47$. Let $\hat{a}$ the number in sequence $\{a_1, a_2, \dots, a_{15}\}$ which corresponds to $\hat{q}$. Then $\dfrac{\hat{a}}{\hat{q}}$ is divisible by some prime number greater or equal that $\hat{q}$. Thus $\hat{a}\geqslant \hat{q}^2 \geqslant 47^2=2209>2005$. We get contradiction. Hence $n_0=14$.

So desired answer to our initial problem is $14+1=15$. Is my reasoning correct?

  • 1
    $\begingroup$ The squares of those primes are not all less than $2005$. $\endgroup$ – lulu Nov 4 '17 at 11:17
  • 1
    $\begingroup$ Note: your argument appears to work perfectly if you apply it to $\sqrt {2005}$. I think, though, that you need a line or two to explain why your set is maximal. $\endgroup$ – lulu Nov 4 '17 at 11:18
  • $\begingroup$ Hmm. I knew that $p_{304}<2005$ but I did not pay attention to it's square which is certainly greater than 2005. Nice comment. Plus for it! $\endgroup$ – ZFR Nov 4 '17 at 11:20
  • $\begingroup$ Once you rectify this, your argument is sound, since $\pi(\lfloor \sqrt{2005}\rfloor) + 1 = 14 + 1 = 15$. $\endgroup$ – астон вілла олоф мэллбэрг Nov 4 '17 at 11:22
  • $\begingroup$ @астонвіллаолофмэллбэрг, Yes I got it. $\endgroup$ – ZFR Nov 4 '17 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.