Prelim 24 & 25 J.O.

24. (Preliminary for Th, March 29; finalized Sat, April 7) Complete our proof of the fundamental theorem of arithmetic by proving uniqueness of prime factorization up to the order of writing the elements. (On 3-27-18 we did existence and Euclid's Lemma: if a prime p divides ab, then either p divides a or it divides b.)

Pf:

Use induction on a number:
WTS: $\forall n\in \mathbb{N} \longrightarrow n=\prod_{i=1}^{n}P_i^{m_i} is unique$

Base case: $n=2$
IH: It works up to some $n\leq N$
IS: WTS: $N=\prod_{i=1}^nP_{i}^{m_i}$ unique

$N=\prod_{i=1}^nP_{i}^{m_i}=\prod_{i=1}^pq_{j}^{n_j}$
If we pick some prime and factor it out, then they will have the same factor and then we show that even then if we add it back they are still equal.

25. (Preliminary for Th, March 29; finalized Sat, April 7) 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.

If $a,b$ are nonnegative integers, then $ab$ is a common multiple. Thus, the set of common multiples is nonempty and has a unique least element by the least element property of natural numbers.

b. Characterize the least common multiple using prime factorization. Use this to give an equation relating LCM and GCD.
$GCD(a,b) \cdot LCM(a,b) = a\cdot b$

c. Define what we should mean by the GCD and LCM of a collection {a1,…,ar} of positive integers. Once you have defined these notions, explain algorithms for computing them.

GCD: Euclid Algorithm
input: $m\leq n$ that are positive integers
Outpud: $GCD(m,n)$

Algorithm: Divide n by m: n=qm+r for some q,r where $0\leq r<m$.
If r=0, then return m. Otherwise, return $Euclid(n,m)$.

LCD: Jordi Algorithm
input: $m\leq n$ that are positive integers
Output: $LCM(m,n)$

Algorithm: Divide n by m. n=qm+r for some q,r where $0\leq r<m$.
If r=0, then return n. Otherwise, return $Jordi(n,m)$.

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