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!
If $s$ is a multiple of both $a$ and $b$, then $s$ is a multiple of $\operatorname{lcm}(a,b)$
-
0@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](http://math.stackexchange.com/a/88411/242) for more. – 2012-01-06
2 Answers
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.