Questions 24 & 25 PreWrite

24. Complete our proof of the fundamental theorem of arithmetic by proving uniqueness of prime factorization up to the order of writing the elements.
Proof: Suppose towards contradiction that there exists an integer $a>1$ that a cannot be written as a product of primes. By the well-ordering principle, there exists a smallest such a. Then, by assumption a is not prime, so a = bc where 1 <b, c<a. Then, b and c can be written as products of prime factors as a is the smallest positive integer than cannot be. But since a = bc, this makes a a product of prime factors.

25. Prove existence and uniqueness of the least common multiple of two positive integers a and b: a positive integer m such that both a and b divide m and m divides any common multiple of the two.
Proof: (Uniqueness) Suppose n and m are both least common multiples. Since they are both least common multiples, we must have both $n|m$ and $m|n$, therefore we must have n = m.
(Existence) Let $A={x \in \mathbb{N}: a|x \wedge b|x}$. A is not empty ($|ab| \in A$ and therefore there is a smallest element of A, m. Since $m \in A, a|m$ and $b|m$. Suppose n is such that $a|n$ and $b|m$, we want to show that $m|n$. Divide n by m: $n = mq + r, 0 \leq r < m$. Then $r = n - mq$. Since $a|n$ and $a|m$ we must also have $a|r$. Similarly, $b|r$ and this forces r = 0. Therefore $m|n$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License