Finalized #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.)


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

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. If a,b are nonnegative integers, then ab is a common multiple of two positive integers. Thus, the set of common multiples is nonempty. Now suppose we have a common multiple of a,b called c. Thus a|c and b|c.
We want to show that c divides any other common multiple. Suppose not. Then for some common multiple m, c does not divide m. Using the division algorithm: c=qm+r. Thus, since a|c, a|m, b|c, and b|m, then a,b must divide r. Since a,b divide c, then r would be a smaller common multiple than c, meeting a contradiction. Thus the existence has been proven.
Now to prove uniqueness, suppose you have two LCMs $m_1, m_2$. If they're both LCMs. then they must divide eachother so then $m_1=m_2$.

b)Suppose you have two numbers a,b and their prime factorization is:
$a=P_{1}^{k_1}\cdot ...\cdot P_{n}^{k_n}$ and $P_{1}^{j_1}\cdot ...\cdot P_{n}^{j_n}$.
Then the LCM = $P_{1}^{max(k_1,j_1)}\cdot ... \cdot P_{n}^{max(k_n,j_n)}$\Note that $k_i+j_i=min(k_i,j_i)+max(k_i,j_i)$\and we defined $GCD(m,n)=P_{1}^{min(k_1,j_1)}\cdot ... \cdot P_{n}^{min(k_n,j_n)}$.
Thus by multiplying and adding exponents:
$LCM(a,b)\cdot GCD(a,b)=a\cdot b$

c)Suppose a collection $A=\{a_1...a_r\}$ contains only 3 elements $a_1,a_2,a_3$. Building on what we have proved before, we want to prove
Let $GCD(a_1,a_2)=G$. Then
Now let $GCD(G,a_3)=\tilde{G}$.
So we know $\tilde{G}$ is the greatest common divisor of $a_1,a_2,a_3$ because it is also $GCD(G,a_3)=GCD((a_1,a_2),a_3))=GCD(a_1,a_2,a_3)$.

To apply this to an algorithm of a collection:

By using what we know above, if we have an algorithm that works up to some element of the collection $a_{n-1}$, then it can work for $a_n$ because we can just do it so that
$GCD(a_1,...,a_{n-1})$ holds, then we can always have it so that
$GCD(a_{n-1},a_n)$ works. So then
$GCD(a_1,...a_n)$ can be done for any collection.

The same holds true of everything for LCM as well.

Just make the algorithms as:

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)$.

Comments - Andrew Furash
Your proof for 24 is a little hand-wavy at the end. I don't think you quite understood the algorithm, we have more than two numbers.

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