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
$GCD(a_1,a_2,a_3)=GCD((a_1,a_2),a_3)$.
Let $GCD(a_1,a_2)=G$. Then
$GCD(G,a_3)=GCD((a_1,a_2),a_3)=GCD(a_1,a_2,a_3)$
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)$.