# Putnam and Beyond #3

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$$.

• 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. – Thomas Andrews Jun 27 at 19:28
• 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. – Thomas Andrews Jun 27 at 19:34
• 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.$ – Thomas Andrews Jun 27 at 19:37
• 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. – Thomas Andrews Jun 27 at 19:53

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.

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