Editing Well-ordering principle (section)

===Prime factorization===
Theorem: ''Every integer greater than one can be factored as a product of primes.'' This theorem constitutes part of the [[Fundamental Theorem of Arithmetic|Prime Factorization Theorem]].

''Proof'' (by well-ordering principle). Let <math>C</math> be the set of all integers greater than one that ''cannot'' be factored as a product of primes. We show that <math>C</math> is empty.

Assume for the sake of contradiction that <math>C</math> is not empty. Then, by the well-ordering principle, there is a least element <math>n \in C</math>; <math>n</math> cannot be prime since a [[prime number]] itself is considered a length-one product of primes. By the definition of non-prime numbers, <math>n</math> has factors <math>a, b</math>, where <math>a, b</math> are integers greater than one and less than <math>n</math>. Since <math>a, b < n</math>, they are not in <math>C</math> as <math>n</math> is the smallest element of <math>C</math>. So, <math>a, b</math> can be factored as products of primes, where <math>a = p_1p_2...p_k</math> and <math>b = q_1q_2...q_l</math>, meaning that <math>n = p_1p_2...p_k \cdot q_1q_2...q_l</math>, a product of primes. This contradicts the assumption that <math>n \in C</math>, so the assumption that <math>C</math> is nonempty must be false.<ref name='mit' >{{cite book |last1=Lehman |first1=Eric |last2=Meyer |first2=Albert R |last3=Leighton |first3=F Tom |title=Mathematics for Computer Science |url=https://courses.csail.mit.edu/6.042/spring17/mcs.pdf |access-date=2 May 2023}}</ref>