0

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.

joriki
  • 238,052
Leric
  • 1

1 Answers1

1

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?

G Tony Jacobs
  • 31,218
  • here is my draft of the answer, could you check if it exists any errors? suppose S is nonempty, S contains at least one element then since S is a nonempty set of natural numbers, S has a least element, call this element n0, n is not prime, it would be factored into itself , so n is composite.? – Leric Apr 21 '18 at 17:54