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?
Best Answer
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.