Either of these proofs are fine. I would propose rewriting the second proof more simply - it's true that you could use induction to prove a statement such as:
The $k^{th}$ composite number can be written as a product of primes.
However, this is a bit silly - since now you have to handle primes and composites separately, even though the same logic applies. It also has the issue that you're writing a proof without knowing which number in particular you're applying it to - you could get in trouble if you had to use more specifics about the number in question but could only say "it's the $1000^{th}$ composite number."
It's easier just to write the proof by strong induction on $n$ itself:
We will prove by strong induction that every $n\geq 2$ can be written as a product of primes. If $n$ is prime, the claim is trivial. Otherwise, we can write $n=ab$ for $2\leq a,b < n$ and use strong induction to rewrite $a$ and $b$ as products of primes - and multiplying these products together gives $n$ as a product of primes.
The comments raised some questions of using strong induction vs. using well-ordering; I think your proofs make appropriate use of both - essentially, your proofs provide algorithms of finding a prime factor or a prime factorization respectively. Your first proof says:
Test every number from $2$ up to $x$ to see which are divisors of $x$. Note that $x$ is assured to be a divisor of $x$, but there may be others. Let $y$ be the least such divisor.
This gives us an iterative algorithm for extracting prime divisors of numbers - and, in general, uses of the well-ordering theorem correspond to an algorithm like this*.
The second proof corresponds to a recursive algorithm:
Check whether $n$ is prime. If so, note that $n=n$ is a prime factorization. If not, write $n=ab$ and recursively apply this algorithm to both $a$ and $b$ and combine the resulting prime factorizations.
The fact that this algorithm finishes is provided by strong induction - since, to factor $n$, we are only going to try to apply the algorithm to smaller inputs, and we can only do that for so long.
These algorithms correspond to the intuition behind the two proofs - indicating that you made a good choice in which to use (and also indicating, as was brought up in comments, that your proofs are constructive - they provide an algorithm for producing the objects they claim exist). It's possible, though not advisable, to rewrite the second proof to start with:
Suppose that it's not true that all $n\geq 2$ have a prime factorization. Let $n$ be the least number without a prime factorization. ...
This would be considered inelegant because it uses proof by contradiction, but could be rephrased as a direct proof without changing the structure of the argument. Note that writing a proof this way also makes it nonconstructive - if I want to actually factor $289$, it doesn't help me to know why there can't be a number that doesn't have a prime factorization! Which is to say: it's a good thing you didn't write a proof that started this way. :)
(*This assumes you have an algorithm to test whether something is in the given set - but, for the set of divisors of $x$, that's clearly possible)
Best Answer
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.