Questions 24 & 25 Post Write

24. Prove uniqueness of prime factorization up to the order of writing the elements.
Proof: We can prove that any integer $n > 1$ either is prime or has a unique factorization by induction. The base case, $n=2$, is clearly prime. We then assume that every integer $1<k < n$ is either prime or has a unique prime factorization. Now suppose that $n$ can be factored as $n = p_1 · p_2 · . . . · p_r, n = q_1 · q_2 · . . . · q_s$ where $r, s \in \mathbb{N}$ and $p_i, q_j$ are prime factorizations of $n$. Without loss of generality, assume towards contradiction that $p_1 ≤ q_1$. Since $1 \neq p_1$ and $q_1$ is prime, $p_1 \nmid q_1$. Using Euclid’s Lemma, it follows that $p_1 |q_{j0}$ for some $j_0 > 1$. Since $q_{j0}$ is prime and $p_1 \neq 1$, $p_1 = q_{j0}$. This is a contradiction.

25. a. 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$.

b. Characterize the least common multiple using prime factorization. Use this to give an equation relating LCM and GCD.
$a = p^{k_1}_1+ p^{k_2}_2+…+ p^{k_n}_n = \Pi_{i=1}^{k} p_i^{n_i}$
$b = p^{l_1}_1+ p^{l_2}_2+…+ p^{l_m}_m = \Pi_{i=1}^{l} p_i^{m_i}$
$LCM(a, b) = \Pi_{i=1}^{max(k, l)} p_i^{max(n_i, m_i)}$
$GCD(a, b) = \Pi_{i=1}^{min(k, l)} p_i^{min(n_i, m_i)}$
If $d = GCD(a, b)$ and $h = LCM(a, b)$, then $d·h = |ab|$.
$(p^(k_1)_1+ p^(k_2)_2+…+ p^(k_n)_n)·( p^(l_1)_1+ p^(l_2)_2+…+ p^(l_m)_m) = \Pi_{i=1} p_i^{min(n_i, m_i)+ max(n_i, m_i)}$
$(p^(k_1+l_1)_1+ p^(k_2+l_2)_2+…+ p^(k_n+l_n)_n) = \Pi^n_{i=1} p_i^{n_i + m_i)}$

c. Define what we should mean by the GCD and LCM of a collection $\{a_1,\dots,a_r\}$ of positive integers. Once you have defined these notions, explain algorithms for computing them.
Lemma 1
Statement: $GCD(a, c) = GCD(b, c) = n$ for some arbitrary $n$ if and only if $GCD(ab, c) = n$.
Proof: If $GCD(ab, c) = n$ then, using the division algorithm, we can write $abx + cy = n$ for some $xy$. But, this says that $a(bx) +cy = n$ which shows that $GCD(a, c) = n$. Similarly, we have $b(ax) +cy = n$ which shows that $GCD(b, c) = n$. Now assume that $GCD(a, c) = GCD(b, c) = n$. Thus we have, for some $u, v, x, y, n = au+cv = bx+cy$ Multiplying these $n = (au+cv)(bx+cy)= ab(ux) + (auy +bvx+cvy)c$ and thus $GCD(ab, c) = n$.//
Proof: The GCD of a set of positive integers is the greatest common denominator that can divide all of the given integers (i.e. $x|a_1…x|a_r$). The LCM of a set of positive integers is the lowest integer that is a multiple of any set of given integers (i.e. $a_1|x…a_r|x$).
Using Lemma 1 above, $GCD(a_1, a_2, a_3, …, a_r)$ is the same as $GCD(GCD(GCD(a_1, a_2), a_3), … a_r)$. Similarly, $LCM(a_1, a_2, a_3, …, a_r)$ is the same as $LCM(LCM(LCM(a_1, a_2), a_3), … a_r)$