I have to prove the following:

$a \equiv b \mod m \wedge a \equiv b \mod n \Rightarrow a \equiv b \mod lcm(m,n)$

I already tried but I'm stuck.

This is what I've got so far:

$m\mid (a-b) \wedge n\mid (a-b) \Rightarrow lcm(m,n)\mid (a-b)$

When trying it with numbers it makes sense. The $lcm$ is never greater than $(a-b)$ and it always is a divisor.

Furthermore I wrote it like this:

$q_{1}\cdot m = a-b \\ q_{2}\cdot n = a-b \\ \Rightarrow q_{3}\cdot lcm(m,n) = a-b$

From the first two lines I get:

$q_{1}\cdot m = q_{2}\cdot n$

But now I am stuck. If this last line was somehow a definition of the $lcm$ that would solve everything, but I didn't find a notation of the $lcm$ like this on the internet.

Was my approach right and can someone point me in the right direction from here or is there a completely other way to prove this?

  • 2
    $\begingroup$ Your first line is all the proof you need, because for any fixed positive integer $k$ by definition $a \equiv b \pmod{k}$ if and only if $k \mid (a-b)$. $\endgroup$ – A.P. Mar 30 '15 at 9:36
  • $\begingroup$ You mean this line? $a \equiv b \mod m \wedge a \equiv b \mod n \Rightarrow a \equiv b \mod lcm(m,n)$ I only rewrote the assignment into the division format... $\endgroup$ – Thursday Next Mar 30 '15 at 9:41
  • 1
    $\begingroup$ Sorry, I assumed you already knew that $a \mid c$ and $b \mid c$ imply $\text{lcm}(a,b) \mid c$ for any three integers $a,b,c$. $\endgroup$ – A.P. Mar 30 '15 at 10:35
  • $\begingroup$ Would you have a link to a prove for that? Because if I knew how to prove that I could use it too for this assignment. $\endgroup$ – Thursday Next Mar 30 '15 at 10:50
  • $\begingroup$ To be able to do that I must ask: how did you define the least common multiple of two integers? $\endgroup$ – A.P. Mar 30 '15 at 10:55

Using the fundamental theorem of arithmetic one can write

$m=\prod_p p^{M_p}$

$n=\prod_p p^{N_p}$

$lcm(m,n)=\prod_p p^{\max(N_p,M_p)}$

where $p$ are prime numbers and $N_p,M_p$ non-negative integers (one can have $N_p=0$ or $M_p=0$). Now, if $m|a-b$ and $n|a-b$ that means that $p^{M_p}|a-b$ and $p^{N_p}|a-b$ and therefore $p^{\max(N_p,M_p)}|a-b$ for any prime number $p$. Now if

$a-b=\prod_p p^{C_p}$

and therefore $C_p\ge\max(N_p,M_p)$. This implies that $lcm(m,n)|a-b$.

  • $\begingroup$ Ahh yes two weekly assignments ago we used the $lcm$ with the prime factorization and the product series (?) notation. This will work, thanks! $\endgroup$ – Thursday Next Mar 30 '15 at 10:10
  • $\begingroup$ One question, did you omit the $\prod_p$ on $p^{M_p}|a-b$ and the such on purpose, or is it just a shortened version? $\endgroup$ – Thursday Next Mar 30 '15 at 10:51
  • 1
    $\begingroup$ It is not a shortened version. The purpose is to show that $p^{\max(N_p,M_p)}$ divides $a-b$. $\endgroup$ – sintetico Mar 30 '15 at 13:48

This is an immediate consequence of the more general fact (which may be taken as the definition of least common multiple) $$ a \mid c \; \wedge \; b \mid c \Rightarrow \text{lcm}(a,b) \mid c $$ for any positive integers $a,b,c$. You can prove it in various ways, one of which is simply substituting "$c$" instead of "$a-b$" in sitentico's answer. Here's another way:

Write $\ell = \text{lcm}(a,b)$. If $\ell \nmid c$ then by unique factorization there are a prime $p$ and integers $h > k \geq 0$ such that $p^h \mid \ell$, $p^k \mid c$, and $p^h \nmid c$. However, $p$ must appear with exponent $h$ in the factorisation of at least one of $a$ or $b$, because by hypothesis $\ell$ is the smallest common multiple of $a$ and $b$. But then, by transitivity, $a \mid c$ and $b \mid c$ imply $p^h \mid c$, which is a contradiction.

  • $\begingroup$ Why does $p^h\vert\ell$ and $p^k\vert c$ imply that $\ell>c$? $\endgroup$ – Sha Vuklia Sep 2 at 20:48
  • $\begingroup$ @ShaVuklia Congratulations for spotting an almost 4 year old mistake! For some odd reason I was following the structure of a gcd argument, not an lcm one... $\endgroup$ – A.P. Sep 3 at 9:15
  • $\begingroup$ Nice, thanks for correcting:D $\endgroup$ – Sha Vuklia Sep 3 at 17:34

The question surprises me, because (as the answer of A.P. also points out) this is immediate from the definition of least common multiple as I teach it: the least common multiple of $m,n$ is a positive common multiple of $m,n$ that divides every other common multiple of $m,n$. In your situation the hypotheses give that $a-b$ is a common multiple of $m,n$, so necessarily it is a multiple of $\def\lmn{\operatorname{lcm}(n,m)}\lmn$.

But even if you use a definition that just says $\lmn$ is the smallest common multiple of $n,m$ (as I suppose you do), then it is still easy to see it divides all other common multiples (and to be honest, this is a necessary check in order to ensure that a least common multiple according to my stronger requirement exists). This does need anything complicated like (unique) factorisation into primes. Like the sets of multiples of $m$ or $n$ individually, the set of common multiples of $m,n$ is closed under taking differences. It also clearly contains all multiples of $\lmn$. But then it cannot contain any other number, because that number would be closer than $\lmn$ to one of those multiples, and the (positive) difference would be a common multiple of $m,n$ less than $\lmn$, contradicting its definition.


That $\ a,b\mid m\,\Rightarrow\,{\rm lcm}(a,b)\mid m\ $ may be conceptually proved by Euclidean descent as below.

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, by induction, we deduce $\,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 the least $\rm\:\ell\in S\,$ divides every element of $\,\rm 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,$ because mod is simply 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.