Problem 25 A B Proof

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.


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.

prove x=y
assume not
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}$

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.

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