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