Can't understand a proof: Let $a,b,c$ be integers. If $a$ and $b$ divide $c$, then $lcm(a,b)$ also divides $c$ Can't understand a proof: Let $a,b,c$ be integers. If $a$ and $b$ divide $c$, then $lcm(a,b)$ also divides $c$
Proof I've been shown: 
Since $c$ is a common multiple of $a,b$, it means that $lcm(a,b) \leq c$.
So:
$c=q\cdot lcm(a,b)+r$, $q \in \mathbb Z$ and $0\leq r \leq lcm(a,b)$
Since $c$ and $lcm(a,b)$ are common multiples of $a,b$, then so is $r$. But $m$ is the least common divisor, then it means $r=0$. 
[Proof taken from: http://www.math.utah.edu/~wood/4400/hw1sol.pdf]
I cannot understand the last step... Why does it imply that $r=0$? 
Thank you! 
 A: It follows from the (general) fact that if $a$ divides $b$ and $c$, then $a$ also divides $b-c$, so in this case:
$c = q.lcm(a,b) + r$ and $0 \leq r < lcm(a,b)$
$c - q.lcm(a,b) = r$
Which means that both $a$ and $b$ divides $r$, but $0 \leq r < lcm(a,b)$. So $r$ must be equal to $0$, and we get:
$c = q.lcm(a,b)$, as you wish.
A: The statement needs no proof, given that you define things properly. See also: partially ordered set, lattice, semilattice, join, meet.
Definition 0. Given $a,b \in \mathbb{N},$ lets say that $a$ divides $b$ iff there exists $k \in \mathbb{N}$ with $ka=b$. We denote this $a \mid b$.
Exercise: Show that $\mid$ is a partial order on $\mathbb{N},$ and verify that $1$ is the least element and $0$ is the greatest element with respect to this order.
Definition 1. Given $a,b \in \mathbb{N},$ the lowest common multiple of $a$ and $b$, denoted $\mathrm{lcm}(a,b),$ is the unique natural number such that for a generic natural number $n$, we have the following equivalence.
$$(a \mid n) \wedge (b \mid n) \leftrightarrow \mathrm{lcm}(a,b) \mid n$$
Exercise: Show that $\mathrm{lcm}$ is a well-defined function. (Technically, what' you're trying to do is to show that binary joins exist in the poset of natural numbers ordered by division.)
A: Hint $ $ The set of all common multiples of $\rm\,a,b\,$ is closed under subtraction thus, by the lemma below, every common multiple is a multiple of the least positive common multiple.
Lemma $\ \ $ If $\,\rm S\,$ is a nonempty set of positive integers closed under positive subtraction (i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\  n-m\, \in\, S)\,$ then every $\rm\,s\in S\,$ is a multiple of the least  $\rm\:\ell = \min\, S.$
Proof ${\bf\ 1}\,\  $ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra  $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$
Proof ${\bf\ 2}\,\rm\,\ \   S\,$ closed under subtraction $\rm\,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod is simply repeated subtraction, i.e. $\rm\ a\ mod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\ $ Therefore $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is in $\,\rm S\,$ and smaller than $\rm\,\ell,\,$ contra minimality of $\rm\,\ell.$ 
Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$\ \ \rm\begin{eqnarray} S\ closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\
&\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
The Lemma describes a fundamental property of natural number arithmetic whose essence will become clearer when one studies ideals of rings (viz. $\,\Bbb Z\,$ is Euclidean $\Rightarrow$ PID). 
A: Origin - https://sp.eths.k12.il.us/aginr/indstudy/Class%20Documents/hw7-solns.pdf
Name  $c$ as a common multiple of $a,b$. Question postulates $\color{brown}{a|c,b|c}$. By definition of $lcm$, $\color{Brown}{a|lcm(a,b), b|lcm(a,b)}$. Defintion of $lcm$ additionally means that $lcm(a,b) \leq c$.
By cause of the Division Algorithm, 
$c=q\cdot lcm(a,b)+r$, for some $q \in \mathbb Z$, such that $0\leq r \leq lcm(a,b)$
$\iff r = c - q*lcm(a,b)$.
By reason of Why if $a = qb + r$, then $\operatorname{gcd}(a,b) = \operatorname{gcd}(b, r)$ intuitively?, the brown statements imply $r|a, r|b$. 
Since r < m and m is their least common multiple, $r|a, r|b$ means the only possibility for r is 0.  
A: I think it's easier using examples. if a=1, b=5, lcm=5.
If we pick c, a common multiple of 1 and 5, such as c=10 for example,
then c=q.lcm : in this case 10 = 2 * 5 + r
since lcm is the least common divisor, it means it is a direct multiple, so r=0 as seen from the example.
