Cualquiera de estas pruebas está bien. Yo propondría reescribir la segunda prueba de manera más simple - es verdadero que podrías utilizar la inducción para demostrar una afirmación como:
El $k^{th}$ El número compuesto se puede escribir como un producto de primos.
Sin embargo, esto es un poco tonto, ya que ahora hay que manejar los primos y los compuestos por separado, aunque se aplique la misma lógica. También tiene el problema de que estás escribiendo una prueba sin saber a qué número en particular la estás aplicando - podrías meterte en problemas si tuvieras que usar más detalles sobre el número en cuestión pero sólo pudieras decir "es el $1000^{th}$ número compuesto".
Es más fácil escribir la prueba por inducción fuerte sobre $n$ sí mismo:
Demostraremos por inducción fuerte que toda $n\geq 2$ se puede escribir como un producto de primos. Si $n$ es primo, la afirmación es trivial. En caso contrario, podemos escribir $n=ab$ para $2\leq a,b < n$ y utilizar la inducción fuerte para reescribir $a$ y $b$ como productos de primos - y multiplicando estos productos entre sí se obtiene $n$ como un producto de primos.
Los comentarios plantean algunas cuestiones sobre el uso de la inducción fuerte frente al uso de la ordenación; creo que tus pruebas hacen un uso apropiado de ambos - esencialmente, tus pruebas proporcionan algoritmos para encontrar un factor primo o una factorización prima, respectivamente. Su primera prueba dice:
Prueba cada número de $2$ hasta $x$ para ver cuáles son los divisores de $x$ . Tenga en cuenta que $x$ se asegura que es un divisor de $x$ pero puede haber otros. Dejemos que $y$ sea el menor de dichos divisores.
Esto nos da un algoritmo iterativo para extraer los divisores primos de los números - y, en general, los usos del teorema del buen orden corresponden a un algoritmo como éste*.
La segunda prueba corresponde a un algoritmo recursivo:
Compruebe si $n$ es primordial. Si es así, observe que $n=n$ es una factorización de primos. Si no es así, escribe $n=ab$ y aplicar recursivamente este algoritmo a ambos $a$ y $b$ y combinar las factorizaciones primarias resultantes.
El hecho de que este algoritmo termine es proporcionado por la inducción fuerte - ya que, para factorizar $n$ En este caso, sólo vamos a intentar aplicar el algoritmo a entradas más pequeñas, y sólo podemos hacerlo durante un tiempo.
Estos algoritmos se corresponden con la intuición que hay detrás de las dos pruebas, lo que indica que has hecho una buena elección a la hora de utilizarlos (y también indica, como se ha comentado, que tus pruebas son constructivo - proporcionan un algoritmo para producir los objetos que dicen que existen). Es posible, aunque no recomendable, reescribir la segunda prueba para empezar:
Supongamos que no es cierto que todos $n\geq 2$ tienen una factorización primaria. Sea $n$ sea el menor número sin factorización prima. ...
Esto se consideraría poco elegante porque utiliza la prueba por contradicción, pero podría reformularse como una prueba directa sin cambiar la estructura del argumento. Hay que tener en cuenta que escribir una prueba de esta manera también hace que no sea constructiva - si quiero realmente factorizar $289$ No me sirve de nada saber por qué no puede haber un número que no tenga una factorización prima. Es decir: menos mal que no escribiste una prueba que empezara así :)
(*Esto supone que se tiene un algoritmo para comprobar si algo está en el conjunto dado - pero, para el conjunto de divisores de $x$ (es evidente que eso es posible)
