Mouctar Diallo

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.

existence:

a,b$\epsilon$Z

ab is a multiple of a and b, so we know the set is nonempty

due to well ordering we know that every set must have a least element; since the set of multiples has at least one element, ab, we know a LCM exists.

uniqueness

LCM=x

LCM=y

prove x=y

assume not

x=/=y

by trichotomy we know

x=y | x>y | x<y |
---|---|---|

this doesn't work because we assumed x=/=y | x can't be greater than y because x wouldn't be the least common multiple —> contradiction | y can't be greater than x because y wouldn't be the least common multiple —> contradiction |

therefore x=y meaning there is only one LCM, proving uniqueness

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

a | b | |
---|---|---|

~ Factorization | P_{1}^{a1}P_{2}^{a2}…P_{n}^{an} |
P_{1}^{b1}P_{2}^{b2}…P_{n}^{bn} |

~ LCM | $\prod ^{\max \left(n,t\right)}_{i=1}P^{max(a_{i},b_{i})}_{i}$ | $\prod ^{\max \left(n,t\right)}_{i=1}P^{max(a_{i},b_{i})}_{i}$ |

~GCF | $\prod ^{\max \left(n,t\right)}_{i=1}P^{min(a_{i},b_{i})}_{i}$ | $\prod ^{\max \left(n,t\right)}_{i=1}P^{min(a_{i},b_{i})}_{i}$ |

LCM*GCM=P^{a}P^{b}

this is because the LCM takes the maximum exponent, while the GCD takes the minimum exponent; since there are only two exponents multiplying these two will give you the same thing multiplying the orginals.