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 | P1a1P2a2…Pnan | P1b1P2b2…Pnbn |
~ 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=PaPb
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.