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.

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.

page revision: 1, last edited: 18 Apr 2018 01:57