Mg Problem 24 25

PRELIMINARY:

24) Complete the proof of the fundamental theorem of arithmetic by proving the uniqueness of the prime factorization up to ordering for positive integers greater than 1.

Pf: Consider $n >1 \in \mathbb{Z}$. We will induct on $n$ to prove that for all $n$, prime factorization is unique. First, consider base case $n=2$. Because 2 is prime, we know that it has exactly two factors, 1 and itself. Thus, the only way to express 2 in the form of the product of primes to positive integer powers is $2^1$. Thus, the base case is proven. Now we may assume that for all $n\leq k$, for some k, prime factorization is unique. We must now simply show that prime factorization is unique for $k+1$. There are two cases. If $k+1$ is prime, prime factorization is clearly unique. If $k+1$ is composite, by definition we may divide it by some prime number to yield another positive integer, $m$, with $m \leq k+1$ and $m > 1$. Since division is well defined, regardless of any chosen factorization of $k+1$, $k+1$ dividing by the same prime always produces the same $m$. And since $m<k$, but inductive hypothesis, $m$ has a unique prime factorization. Thus, $k+1$ has a unique prime factorization. $QED$

25) a. Prove the existence and uniqueness of a least common multiple (LCM) of two positive integers $a$ and $b$.

Existence: A common multiple of a and b would be defined as some integer that both a and b divide. Since the positive integers are closed under multiplication, the product of a and b produce an integer that is a common multiple, thus proving the existence of a non-empty set S of common multiples of a and b. And since the positive integers are representations of the naturals and S is a set of positive integers, S has a least element by well ordering. Therefore, we can conclude that any two integers a and b have a least common multiple.

Uniqueness: ROADMAP: Suppose there are two LCMs for given a and b. Show using the generic case that they are in fact the same.

b. Characterize the LCM using prime factorization. Use this to give an equation relating LCM and GCD.

Consider the given prime factorization of a defined as $a = \prod_{i=1}^{j} {{p_i}^{m_i}}$ with $p_i$ the i-th prime and $m_i$ its corresponding exponent, up to the j-th prime, the greatest prime less than or equal to a, and that of b defined similarly as $b = \prod_{i=1}^{k} {{p_{i}}^{n_i}}$. The LCM of a and b would be defined as $\prod_{i=1}^{max(j,k)} {{p_i}^{max({m_i},{n_i})}}$.

With this definition, we can relate the LCM and GCD by the following equation:

(1)
\begin{align} LCM = GCD * \prod_{i=1}^{max(j,k)} {{p_i}^{max({m_i},{n_i})-min({m_i},{n_i})}} \end{align}

c. Define what we should mean by GCD and LCM of a collection $\{a_0,...,a_r\}$ of positive integers. Explain algorithms for computing them.

The GCD of such a collection would be the greatest positive integer, $d$, such that $d|{a_i}$ for all $i \in \mathbb{N} \leq r$. The LCM would be the least positive integer, $m$, such that ${a_i}|m$ for all $i \in \mathbb{N} \leq r$.

To return $d$ for the set $\{a_0,...,a_r\}$, find use the Euclid algorithm to find $d_0 = GCD({a_0},{a_1})$. Repeat to find $GCD({d_{n-1}},{a_n})$ up to $n=r$. $GCD(d_{r-1},{a_r}) = d$.

To return $m$, take the prime factorization of each element of the collection and find the maximum exponent, $M_i$ corresponding to the i-th prime number for all up to $p_q$, the greatest primes less than any of the elements of the collection. Calculate $m =\prod_{i=1}^{q} {{p_i}^{M_i}}$.

FINALS:

24) Complete the proof of the fundamental theorem of arithmetic by proving the uniqueness of the prime factorization up to ordering for positive integers greater than 1.

Pf: Consider $n >1 \in \mathbb{Z}$. We will induct on $n$ to prove that for all $n$, prime factorization is unique. First, consider base case $n=2$. Because 2 is prime, we know that it has exactly two factors, 1 and itself. Thus, the only way to express 2 in the form of the product of primes to positive integer powers is $2^1$. Thus, the base case is proven. Now we may assume that for all $n\leq k$, for some k, prime factorization is unique. We must now simply show that prime factorization is unique for $k+1$. There are two cases. If $k+1$ is prime, prime factorization is clearly unique. If $k+1$ is composite, by definition we may divide it by some prime number to yield another positive integer, $m$, with $m \leq k+1$ and $m > 1$. Since division is well defined, regardless of any chosen factorization of $k+1$, $k+1$ dividing by the same prime always produces the same $m$. And since $m<k$, but inductive hypothesis, $m$ has a unique prime factorization. Thus, $k+1$ has a unique prime factorization. $QED$

25) a. Prove the existence and uniqueness of a least common multiple (LCM) of two positive integers $a$ and $b$.

Existence: A common multiple of a and b would be defined as some integer that both a and b divide. Since the positive integers are closed under multiplication, the product of a and b produce an integer that is a common multiple, thus proving the existence of a non-empty set S of common multiples of a and b. And since the positive integers are representations of the naturals and S is a set of positive integers, S has a least element by well ordering. Therefore, we can conclude that any two integers a and b have a least common multiple.

Uniqueness: Suppose that for generic positive integers $a$ and $b$ there exist two LCMs, $c$ and $d$. Then there would be some set $S = \{a,b\}$ of LCMs. Since an LCM is a positive integer, by well ordering, there exists a least element. Thus, without loss of generality, we may say $a \leq b$. If $a<b$, then there exists a common multiple less than $b$, which would contradict the fact that $b$ is a least common multiple. Therefore, it must be the case that $a=b$. $QED$

b. Characterize the LCM using prime factorization. Use this to give an equation relating LCM and GCD.

Consider the given prime factorization of a defined as $a = \prod_{i=1}^{j} {{p_i}^{m_i}}$ with $p_i$ the i-th prime and $m_i$ its corresponding exponent, up to the j-th prime, the greatest prime less than or equal to a, and that of b defined similarly as $b = \prod_{i=1}^{k} {{p_{i}}^{n_i}}$. The LCM of a and b would be defined as $\prod_{i=1}^{max(j,k)} {{p_i}^{max({m_i},{n_i})}}$.

With this definition, we can relate the LCM and GCD by the following equation:

(2)
\begin{align} LCM = GCD * \prod_{i=1}^{max(j,k)} {{p_i}^{max({m_i},{n_i})-min({m_i},{n_i})}} \end{align}

c. Define what we should mean by GCD and LCM of a collection $\{a_0,...,a_r\}$ of positive integers. Explain algorithms for computing them.

The GCD of such a collection would be the greatest positive integer, $d$, such that $d|{a_i}$ for all $i \in \mathbb{N} \leq r$. The LCM would be the least positive integer, $m$, such that ${a_i}|m$ for all $i \in \mathbb{N} \leq r$.

To return $d$ for the set $\{a_0,...,a_r\}$, find use the Euclid algorithm to find $d_0 = GCD({a_0},{a_1})$. Repeat to find $GCD({d_{n-1}},{a_n})$ up to $n=r$. $GCD(d_{r-1},{a_r}) = d$.

To return $m$, take the prime factorization of each element of the collection and find the maximum exponent, $M_i$ corresponding to the i-th prime number for all up to $p_q$, the greatest prime less than any of the elements of the collection. Calculate $m =\prod_{i=1}^{q} {{p_i}^{M_i}}$.

Comments - Andrew Furash
Looks good. 25b is wrong.

page revision: 23, last edited: 12 Apr 2018 19:40
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License