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!
$\endgroup$ 52 Answers
$\begingroup$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}\:.$
$\endgroup$ $\begingroup$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.
$\endgroup$
