EDIT: I am updating this to illustrate my proof thus far. I would appreciate any critique.

Question details: "Use the well ordering principle to prove that every integer $n\ge2$ has a prime factor.

One way to prove this for a given integer $n\ge2$ is to apply the well-ordering principle to the set

$X=\{d\in{\Bbb Z}:d\ge2 \land d\ |\ n\}$,

the set of all factors $d$ of $n$ such that $d\ge2$.

(a) Prove that $X$ is not empty.

(b) Prove that if $p$ is the minimal element of $X$, then $p$ must be a prime number.

(c) Finish the proof of the theorem."

(a) Trivial. By definition of $X$, $n\in X$ if $n\ge2$. Thus, $X$ is nonempty given any integer $n\ge2$.

(b) Suppose $p$ is the minimal element of $X$. Then, it is a divisor of $n$, and it is also $\ge2$. Consider some integer $q\ge2$ that is a divisor of $p$. Then, $q\in X$ by definition of $X$, since any divisor of $p$ is also a divisor of $n$ (and $q\ge2$). Since $p$ is the minimal element of $X$, then any other element of $X$ $\le p$. Therefore, $q\le p$. Furthermore, $q$ is a divisor of $p$, so $q\ge p$. Then, $q=p$. Thus, $p$ only has two positive integer factors - itself, and 1. Therefore, $p$ is prime.

(c) Suppose, for the sake of contradiction, that there exists a set $C$, of integers $\ge2$ that cannot be factored into a product of two prime numbers. By the well-ordering principle, there is some $m\in C$ such that $m$ is the minimal element of $C$. Because $m\in C$ and therefore cannot be prime, it must be the product of two integers $s,t$ such that $2\le s,t \lt m$. Therefore, $s,t\notin C$ because they are smaller than $m$, which is the minimal element of $C$.

Since $s,t\notin C$, they can be factored into the products of primes, $a_1,a_2,b_1$ and $b_2$ such that $s=a_1*a_2$ and $t=b_1*b_2$. Since $s,t$ are divisors of $m$,

$m=s*t=(a_1*a_2)(b_1*b_2)$, the product of primes.

This is a contradiction, because $m\in C$. Thus, set $C$ cannot exist. As a consequence, we have proved that every integer $n\ge2$ has a prime factor.

[The End]

Have I got it right? If not, please point out any flaws. If I do have it correct, what I would especially appreciate is any input on the proof-writing itself - is it nonsensical or inefficient? Thanks!

  • $\begingroup$ In (b) you correctly proved that if $X$ has a minimum member $p$ then p is prime. In (a) you correctly proved that $X$ is not empty. So you can re-write (c) as "By (a), and the Well-Order Principle, $X$ has a least member $p,$ and by (b), $p$ is prime. QED." $\endgroup$ – DanielWainfleet May 11 '18 at 21:14
  • $\begingroup$ I dk what "the theorem" is in (c). My previous comment assumed it was merely the statement in the Q's title. $\endgroup$ – DanielWainfleet May 11 '18 at 23:58

Given any integer $n$ such that $n\geq2$ the set $X$ as defined above is nonempty since $n\in X$. So there is a minimal element in $X$. Let us call it $p$. Since $p\in X$ we know that $p$ is a divisors of $n$ which is $\geq 2$. Now we show that $p$ must be prime: let $q$ be a divisors of $p$, $q\geq2$. Then $q\in X$ since any divisors of $p$ also is a divisors of $n$. Since $p$ is miñimal in $X$ any element of $X$ must be $\geq p$. In particular $q\geq p$. But $q\leq p$ also since $q$ divides $p$. Thus $p$ is prime.

  • $\begingroup$ Thank you Jens, this is helpful! What you are saying at the end of your comment is that because $q\ge p$ and $q\le p$, then $q=p$. Therefore, the only divisors of $p$ are itself (and 1), and thus it is a prime number. Did I follow you correctly? $\endgroup$ – akot717 May 11 '18 at 2:35
  • 1
    $\begingroup$ In my opinion, yes! $\endgroup$ – Jens Schwaiger May 11 '18 at 2:36

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.