# If $s$ is a multiple of both $a$ and $b$, then $s$ is a multiple of $\operatorname{lcm}(a,b)$

I came across this as I was doing work for one of my classes. We just use this property, proved presumably in number theory, which we didn't need to take. Could someone help me? Prove that if $a$, $b$ are positive integers, and $m=\operatorname{lcm}(a,b)$, and if $s$ is a multiple of both $a$ and $b$, $s$ is a multiple of $m$. I tried representing each as a multiple, decomposing them, but I don't think I am getting it. I think I am missing some property. Thanks, especially if you could explain this using basic methods!

-
The property you want to prove is the way LCM is normally defined. (This is evident from the name: least common multiple.) What is your definition of the LCM? –  Srivatsan Jan 6 '12 at 3:11
@Srivatsan I think you're mistaken. The lcm is simply the smallest one among all common multiples. Therefore all others are bigger than it. But "bigger than" is not the same as "multiples of". –  Michael Hardy Jan 6 '12 at 4:08
@Michael That is a valid point, thanks for pointing it out. But I stand by my comment; see this question and my answer for an explanation. I do agree that under the definition I am imagining, there is an additional task of proving that the LCM/GCD exists. // Of course, it is likely that the OP defines it the way you do, but I would like to point out another point of view nevertheless. –  Srivatsan Jan 6 '12 at 4:33
@Michael Hardy: The disadvantage of this definition, is that if you do the same for gcd, then $gcd(0,0)$ is undefined (zero is a multiple of any integer). However, it is better to define it as 0, integers with $gcd$ then form a monoid etc. –  sdcvvc Jan 6 '12 at 6:12
@MichaelHardy For Euclidean domains one can indeed define LCM as a common divisor of least Euclidean value (= least absolute value in $\mathbb Z$), and dually for GCD. But generally one has no such structure available so one has to use the universal definition employing extremality w.r.t. divisibility, i.e. the property whose proof is sought in the question. See my post here for more. –  Bill Dubuque Jan 6 '12 at 20:58

HINT $\$ Apply the following basic Lemma to the set $\rm\:M\:$ of positive common multiples of $\rm\:a,b\:.$
LEMMA $\ \$ If a nonempty set of positive integers $\rm\: M\:$ satisfies $\rm\ n > m\ \in\ M \ \Rightarrow\ \: n-m\ \in\ M$
then every element of $\rm\:M\:$ is a multiple of the least element $\rm\:m_{\:1} \in M\:.$
Proof $\ \:$ If not there is a least nonmultiple $\rm\:n\in M\:,$ contra $\rm\:n-m_{\:1} \in M\:$ is a nonmultiple of $\rm\:m_{\:1}\:.$
The key is to factor $a$ and $b$ into primes. Let $$a = p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}, b = q_1^{d_1}q_2^{d_2}\cdots q_x^{d_x}$$ where the $p_i$'s are distinct from each other, as are the $q_i$'s. Anything that is a multiple of $a$ is divisible by each $p_i$ at least $c_i$ times, while any multiple of $b$ is divisible by each $q_i$ at least $d_i$ times. Hence anything divisible by both most be the product of some number and all the distinct prime factors of $a$ and $b$ raised to whichever exponent ($c_i$ or $d_i$) is larger, and this includes the least common multiple (which must be the one that is only divisible by these primes). Hence it is a product of some number and the least common multiple.