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

Question

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.

Answer 1

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

Answer 2

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