Use the Well-Ordering Principle to prove the Fundamental Theorem of Arithmetic, i.e. the existence and uniqueness of the prime factorization of any natural number.
hi dear all, I checked two videos of the theorems on Youtube, but I don't know how to combine them together to solve the question. well-ordering principle: every non-empty subset of positive integers has at least an element.
Fundamental Theorem of Arithmetic: According to the video that I watched on Youtube, the factorization of n into product of primes is unique except for the order the factors.
ok, now I understand the meaning of well-ordering principle, but I am not sure about the Fundamental Theorem of Arithmetic, and how can we combine the two theorems to solve this problem?
thanks.
HINT: Suppose there is a number that does not have a unique prime factorization. Then the set of all natural numbers that do not have unique prime factorizations forms a non-empty set of positive integers. Hence, it has a least element $n_0$, meaning every positive integer less than $n_0$ does have a unique prime factorization.
Now think about $n_0$. Is it prime? Is it composite? Do both options lead to contradictions?