Proving that any common multiple of two numbers is a multiple of their least common multiple I'm trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multiple is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple $q$ of $n,m$ is a multiple of $k$, so that there exists a $g$ so that $q=k·g$.
Logically it seems correct, but I can't seem to prove it... Any help?
 A: We know that $n$ and $m$ divide both $k$ and $q$.
Since $k$ is the lowest common multiple, $k \leq q$.
If $k = q$ then the result is obvious.
Let's assume that $k < q$
Then we can do the integer division between $k$ and $q$:
$q = t·k + r$ so that $0 \leq r < k$.
Since $n$ and $m$ divide $q$ and $k$ then they divide $q - t·k = r$. Therefore $n$ and $m$ divide $r$. But $r < k$, and $k$ is the lowest common multiple.
Therefore $r = 0$ what means that $q = t·k$ for some integer $t$.
A: This is a typical Euclidean descent. The set $M$ of all positive common multiples of $\,a,b\,$ is closed under positive subtraction, i.e. $\,m> n\in M$ $\Rightarrow$ $\,a,b\mid m,n\,\Rightarrow\, a,b\mid m\!-\!n\,\Rightarrow\,m\!-\!n\in M.\,$ Therefore, further, $\,M\,$ is closed under mod, i.e. remainder, since it arises by repeated subtraction, i.e. $\ m\ {\rm mod}\ n\, =\, m-qn = ((m-n)-n)-\cdots-n.\,$ Therefore it follows that the least positive $\,\ell\in M\,$ divides every  $\,m\in M,\,$ else $\ 0\ne m\ {\rm mod}\ \ell\, $ would be an element of $\,M\,$ smaller than $\,\ell,\,$ contra minimality of $\,\ell.\,$  Thus the least common multiple $\,\ell\,$ divides every common multiple $\,m.$
Remark $\ $ The key structure exploited in the proof is abstracted out in the Lemma below. 
Lemma $\ \ $ Let $\,\rm S\ne\emptyset \,$ be a set of integers $>0$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\  n-m\, \in\, S.\,$  Then every element of $\rm\,S\,$ is a multiple of the least element $\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 may be computed by repeated subtraction, i.e. $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Thus $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\in S\,$ and smaller than $\rm\,\ell,\,$ contra mimimality 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}$
Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. 
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). 
