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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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