# Prove a ≡ b mod m ∧ a ≡ b mod n ⇒ a ≡ b mod lcm(m,n) (Stuck midway through solution)

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?

• 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)$. – A.P. Mar 30 '15 at 9:36
• 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... – Thursday Next Mar 30 '15 at 9:41
• 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$. – A.P. Mar 30 '15 at 10:35
• 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. – Thursday Next Mar 30 '15 at 10:50
• To be able to do that I must ask: how did you define the least common multiple of two integers? – A.P. Mar 30 '15 at 10:55

## 4 Answers

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

• Ahh yes two weekly assignments ago we used the $lcm$ with the prime factorization and the product series (?) notation. This will work, thanks! – Thursday Next Mar 30 '15 at 10:10
• 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? – Thursday Next Mar 30 '15 at 10:51
• It is not a shortened version. The purpose is to show that $p^{\max(N_p,M_p)}$ divides $a-b$. – 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.

• Why does $p^h\vert\ell$ and $p^k\vert c$ imply that $\ell>c$? – Sha Vuklia Sep 2 at 20:48
• @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... – A.P. Sep 3 at 9:15
• Nice, thanks for correcting:D – 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).