1
$\begingroup$

I have a solution but I am confused why this book uses more abstruse language or I am missing something (as in are my solutions not rigorous enough):

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. The solution from Putnam and Beyond uses contradiction and least/maximums of prime factorizations. I think the solutions are basically the same, but the Putnam one has me a bit confused.

Here's mine:

Since the set of positive integers is relatively prime, each positive integer is comprised of the primes $2,\dots,43$. Considering a set of no primes, we can use powers of these primes to construct the set, the largest set of which being the squares of the primes from $2,...,43$ which has $14$ elements.

In order for the set to remain pairwise relatively prime any new integer appended to the set must have be divisible by a prime greater than $43$. The smallest being $47$. Since the set must be comprised of composite numbers, the smallest number that satisfies this property is $47^2$ which is greater than $2005$. So any such set with at least $n = 15$ elements must have at least one prime number and from above it is seen that we can construct sets that have pairwise relatively prime integers and are composite for $n < 15$ by considering n squares of primes. Hence $n = 15$.

$\endgroup$
  • $\begingroup$ Your first sentence this is only true if the set doesn't contain primes (like, say, $101.$) So you are implicitly using proof by contradiction. Why can't $202$ be in your set? Also, break your answer into paragraphs. Very hard to read one long paragraph. $\endgroup$ – Thomas Andrews Jun 27 at 19:28
  • 1
    $\begingroup$ You've shown that one set of $14$ relatively prime and non-prime values cannot be extended to $15.$ But .that doesn't show it for all sets of $14$ non-prime relatively prime values. $\endgroup$ – Thomas Andrews Jun 27 at 19:34
  • 1
    $\begingroup$ The basic argument is that if $m$ is not prime and in $2,\dots,2004,$ then $m$ is divisible by a prime in $2,\dots,43.$ $\endgroup$ – Thomas Andrews Jun 27 at 19:37
  • $\begingroup$ Your intuition is correct, but there are other sets. For example: $\{2p_{27},3p_{26},5p_{25},\cdots,41p_{15},43^2\}$ is another example of 14 non-primes relatively prime. $\endgroup$ – Thomas Andrews Jun 27 at 19:53
3
$\begingroup$

You've shown that one set of $14$ relatively prime and non-prime values cannot be extended to $15.$ But that doesn't show it for all sets of $14$ non-prime relatively prime values. Another $n=14$ example set is $\{2p_{27},3p_{26},5p_{25},\cdots,41p_{15},43^2\},$ where $p_{15}=47,p_{16}=53,\dots,p_{27}=103.$

Your instinct is correct, but it is just not a complete proof.

This is a neat problem, because the intuition feels instinctive, but proving it correctly requires some technique.


Given any $m>1$, define $d(m)$ to be the smallest prime divisor of $m.$

Claim 1: If $2\leq m\leq 2004$ is not prime, $d(m)\leq 43.$

Proof: Otherwise, $m\geq p_1p_2$ for some pair of primes $p_1,p_2$ and $p_i\geq 47.$ But then $m\geq 47^2=2209.$


Claim 2: If $m_1,m_2>1$ are relatively prime, then $d(m_1)\neq d(m_2).$

Proof: If $p=d(m_1)=d(m_2)$ then $p$ us a common factor of $m_1$ and $m_2.$


Claim 3: Given any set $S=\{m_1,\cdots,m_{15}\}$ of non-prime values with $2\leq m_i\leq 2004.$ Then the set is not pairwise relatively prime

Proof: There are at most $14$ distinct possible values of $d(m_i)$ by claim $1,$ since there are $14$ distinct primes $\leq 43$. Thus $d(m_i)=d(m_j)$ for some $i\neq j.$ Then by claim $2,$ $m_i$ and $m_j$ are not relatively prime.


Your example of the squares $S=\{2^2,\cdots,43^2\}$ shows that $n=15$ is the smallest such $n$ for which it is true.

$\endgroup$
  • $\begingroup$ Your fourth comment helped a lot, thanks. $\endgroup$ – Derek Luna Jun 27 at 20:32
  • $\begingroup$ I was confused in thinking I was only going to be able to use primes $\le$ 43... $\endgroup$ – Derek Luna Jun 27 at 20:42

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.