# $a\equiv b\pmod {m_1}, a\equiv b\pmod {m_2} \implies a\equiv b\pmod L$

If $\exists a, b, m_1, m_2 \in \mathbb{Z}, a\equiv b\pmod {m_1}$ and $a\equiv b\pmod {m_2}$, then $\exists k \in \mathbb{Z}, a=b+{m_1m_2k\over gcd(m_1,m_2)} \implies a\equiv b\pmod L$, where $L$ is the l.c.m. of $m_1$ and $m_2$.

I am trying to derive, starting with the first part, with no success

1. $\exists l \in \mathbb{Z}, a -b = l\cdot m_1 \implies a =b +l\cdot m_1$
2. $\exists m \in \mathbb{Z}, a-b = m\cdot m_2 \implies a =b +m\cdot m_2$

Equating both, $b +l\cdot m_1 = b +m\cdot m_2$

Unable to start the proof

Based on comment by @saulspatz, the new attempt to proof is:
$\exists r_1, r_2 \in \mathbb{Z},$ s.t.
(i) $m_1 = r_1\gcd(m_1, m_2),$ (ii) $m_2 = r_2\gcd(m_1, m_2)$
Multiplying, (i) by (ii), we get: $m_1m_2 = r_1r_2(m_1, m_2)^2$
if for suitable integer $k$, take $r_1r_2={1\over k}$, then not possible as $r_1, r_2$ are themselves integers.

So, anyway attempt something:
Let, $r_1r_2=k'$, $m_1m_2 = k'(m_1, m_2)^2 \implies (m_1, m_2) = {m_1m_2 \over {k'\cdot (m_1, m_2)}}$

But, $k'$ is an integer, and the final form has an integer $k$ in numerator.

• Well, subtract $b$ from both sides of the last equation, to begin with. – saulspatz Feb 8 '18 at 4:33
• @saulspatz This is not leading me, as : $l\cdot m_1 -m\cdot m_2 =0.$ Please tell how to proceed. – jitender Feb 8 '18 at 4:35
• Try to relate the equation to $\gcd(m_1, m_2).$ You've got to introduce the gcd into the problem somehow, right? Then, what does the gcd have to do with the lcm? – saulspatz Feb 8 '18 at 4:39
• @saulspatz $\gcd (m_1, m_2)\cdot$ lcm$(m_1, m_2) = m_1\cdot m_2$. I could have related to $\gcd,$ if $l\cdot m_1 - m\cdot m_2$ had not been equated to $0$, as $\gcd \gt 0$. – jitender Feb 8 '18 at 4:47
• @jtender I suggest you write $m_1=r_1\gcd (m_1,m_2),$ $m_2=r_2\gcd(m_1,m_2)$ and see where that leads. I haven't done the problem, and I don't plan to. This is my last suggestion. – saulspatz Feb 8 '18 at 5:08

## 2 Answers

Let $M = m*n$ be a multiple of $n$.

Then $a \equiv b \mod n \implies a \equiv b + kn \mod M$ for some $k: 0 \le k <n$. (That's clear: $a = b + v*n = b + (q*m + k)n\equiv b + kn \mod mn$.)

So if we have $L = \text{lcm}(m_1,m_2) = k_1m_1 = k_2m_2$ then

Then if $a \equiv b \mod m_1$ and $a\equiv b \mod m_2$ then $a \equiv b + l_2*m_1 \mod L$ and $a \equiv b + l_2*m_1 \mod L$ where $l_1 < k_1$ and $l_2 < k_2$.

So $l_1*m_1 \equiv l_2*m_2$. Now $0\le l_1*m_1 < k_1m_1 = L$ and $0\le l_2*m_2 , k_2m_2 = L$ so $l_1*m_1 = l_2*m_2$ so $l_1m_1 = l_2m_2$ is a common multiple of $m_1, m_2$.

But $L$ is the least common multiple so $l_1*m_1 = l_2*m_2 = 0$.

======

$a \equiv b \mod m_1$ means $a = b + j*m_1 = b+ j*\gcd(m_1,m_2)*\frac {m_1}{\gcd(m_1,m_2)}$.

And $a\equiv b \mod m_2$ means $a = b + l*m_2 = b + l*\gcd(m_1,m_2)*\frac {m_2}{\gcd(m_1,m_2)}$

So $j*\gcd(m_1,m_2)*\frac {m_1}{\gcd(m_1,m_2)}=l*\gcd(m_1,m_2)*\frac {m_2}{\gcd(m_1,m_2)}$

So $j*\frac {m_1}{\gcd(m_1,m_2)}=l*\frac {m_2}{\gcd(m_1,m_2)}$

But $\frac {m_1}{\gcd(m_1,m_2)}$ and $\frac {m_2}{\gcd(m_1,m_2)}$ are relatively prime.

So $\frac {m_1}{\gcd(m_1,m_2)}|l$ and $\frac {m_2}{\gcd(m_1,m_2)}|j$

So $j*\frac {m_1}{\gcd(m_1,m_2)}=l*\frac {m_2}{\gcd(m_1,m_2)}= k*\frac {m_1}{\gcd(m_1,m_2)}*\frac {m_2}{\gcd(m_1,m_2)}$

And $j*\gcd(m_1,m_2)*\frac {m_1}{\gcd(m_1,m_2)}=l*\gcd(m_1,m_2)*\frac {m_2}{\gcd(m_1,m_2)}= k*\gcd(m_1,m_2)*\frac {m_1}{\gcd(m_1,m_2)}*\frac {m_2}{\gcd(m_1,m_2)}=k*\frac {m_1m_2}{\gcd(m_1,m_2)}$

So $a = b+ k*\frac {m_1m_2}{\gcd(m_1,m_2)}$

And $a \equiv b \mod \frac {m_1m_2}{\gcd(m_1,m_2)}$

And $L = \frac {m_1m_2}{\gcd(m_1,m_2)} =$ lowest common multiple of $m_1, m_2$.

• I would request you to please help in the first part of the proof, as it is not obvious at all. I feel that to show that : $\exists k \in \mathbb{Z}, a=b+{m_1m_2k\over gcd(m_1,m_2)}$ may need approach that considers the two equalities: (i) $a\equiv b\pmod {m_1}$, and (ii) $a\equiv b\pmod {m_2}$ as: $\exists x_1, x_2, k_1,k_2\in \mathbb{Z},$ s.t. (i) $ax_1 = b+m_1k_1,$ & (ii)$ax_2 = b+m_2k_2.$ The conviction that this approach may help, arises out of total failure to approach solution by other way. Also, in another post of mine today, you have shown something similar to this result. – jitender Feb 9 '18 at 23:56
• $\frac {m_1m_2}{\gcd(m_1,m_2)}$ is just the formula for lowest common multiple. So this is just asking to prove that if $a \equiv b \mod m_1$ and $a \equiv b \mod m_2$ then $a \equiv b \mod L$. – fleablood Feb 10 '18 at 0:10
• Not clear about how the equality with three terms with the third term as $k*\frac {m_1}{\gcd(m_1,m_2)}*\frac {m_2}{\gcd(m_1,m_2)}$ appeared. Is it that : $\exists k_1 , k_2$, s.t. $\frac {m_1}{\gcd(m_1,m_2)} = k_1l, \frac {m_2}{\gcd(m_1,m_2)} = k_2j$. But, confused after this, and need help (provided, I am even correct in assuming this). Also, regarding your earlier comment, the value $L$= l.c.m. is for only one value of $k=1$, seemingly the parameter $k$ should serve all divisors of the l.c.m. (again, shaky on that). – jitender Feb 10 '18 at 0:58
• If $c$ and $d$ are relatively prime then if $lc = md$ that means $c|m$ and $d|l$ If we let $l = k_1d$ and $m = k_2d$ then $lc = k_1cd$ and $md = k_2cd$ so $k_1 = k_2$. Call it $k$. then $lc = md = k*c*d$. That's all. – fleablood Feb 10 '18 at 1:04
• Thanks, but a small typo made me breathless. There should be $m=k_2c$ – jitender Feb 10 '18 at 1:18

There are $r$ and $s$ such that $a-b=rm_1$ and $a-b=sm_2$. Therefore $a-b$ is a common multiple of $m_1$ and $m_2$.

Now it depends on what definition of lowest common multiple you use. If the definition is “a common multiple that divides every other common multiple”, then you're done.

If you use the definition “the least positive integer that's a multiple of both $m_1$ and $m_2$, you need to prove that $L$ divides every other positive common multiple.

Suppose $M$ is a positive common multiple of $m_1$ and $m_2$; then $M=Lq+r$, with $0\le r<L$. It is readily verified that $r$ is a common multiple of $m_1$ and $m_2$; hence it must be zero by definition of $L$.

We have proved that $L$ divides $a-b$, that is, $a\equiv b\pmod{L}$.

• Can you please elaborate how $M = Lq+r$, if it is a common multiple of $m_1, m_2$. I mean assuming that $L$ by either of the definition, that it divides every other positive common multiple; then what is $q$. Please give an example, if possible. Else, please state a source. And regarding your statement that : $r$ is too a common multiple of the same, I hope that the linear combination of $M-Lq$ is taken up. – jitender Feb 10 '18 at 1:49
• @jitender That’s the standard division with remainder. – egreg Feb 10 '18 at 9:45
• Please state an example, any simple one. I agree, but the context is totally different. – jitender Feb 10 '18 at 13:32
• @jitender If $M=25$ and $L=7$, then $M=Lq+r$, with $q=3$ and $r=4$. – egreg Feb 10 '18 at 13:43