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?


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$.

  • 1
    $\begingroup$ +1. Although true, I think your second, third and fourth lines may be unnecessary. $\endgroup$ – Henry Jul 26 '14 at 9:28
  • $\begingroup$ I.e. given any two positive common multiples $\,q,k,$ we can find a smaller one $\,q\,$ mod $\,k,\,$ if $\,k\nmid q.\,$ Thus if $\,k\,$ is the least positive common multiple, then it must divide all others (else $\,q\,$ mod $\,k\,$ is a smaller one). This is the key descent step, and it works for any nontrivial set of integers closed under subtraction - see my answer. $\endgroup$ – Bill Dubuque Jul 26 '14 at 16:10

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.