LCM and Congruence.md

LCM and Congruence

Here I show that:

1. The least common multiple of two numbers divides all other multiples of those numbers, and
2. if $a \equiv b ;(\bmod{m})$ and $a \equiv b ;(\bmod{n} )$, for coprime integers $a$ and $b$, $a \equiv b ; (\bmod{mn})$.

The LCM divides all other multiples

The least common multiple of two numbers is the smallest number that they both divide. Let the least common multiple of two numbers $a$ and $b$ be denoted by $\operatorname{LCM}(a, b)$.

Let $L := \operatorname{LCM}(a, b)$, this means that $a\mid L$ and $b \mid L$ ¹. Let $M$ be another common multiple of $a$ and $b$.

$$ (a,b\mid L) \land (a,b\mid M) $$

We would like to show that $L \mid M$, so dividing $L$ by $M$ using integer division, we get the following expression where $r$ is the remainder and $k \in \mathbb{Z}$.

$$ M = Lk + r $$

The properties of division mean that $r \lt L$. We can rearrange our equation to be in terms of $r$.

$$ r = M - Lk $$

We now show that if a number divides both $C$ and $D$, then that number also divides $C-D$.

$$ a\mid C \implies ak_C=C $$

$$ a\mid C \land a|D \iff C-D=ak_C - ak_D = a(k_C - k_D) \implies a \mid C-D $$

Returning to our earlier equation, as $a,b\mid M \land a,b\mid L$, it is also true that $a,b\mid M-Lk$. As $r = M-Lk$, it is also true that $a,b\mid r$, or in other words, $r$ is a common multiple of $a$ and $b$. As $r\lt L$ and $L$ is the least common multiple of $a$ and $b$, it must be the case that $r=0$.

Thus, the least common multiple of two numbers divides all other multiples of those numbers.

Congruence and the LCM

Say that $a \equiv b ;(\bmod{m})$ and that $a \equiv b ;(\bmod{n} )$ and that $a$ and $b$ are coprime integers.

$$ a \equiv b ; (\bmod{m}) = a-b=0;(\bmod{m}) \iff m \mid (a-b) $$

So our earlier statement is equivalent to saying $m,n\mid (a-b)$. In terms of multiples, $a-b$ is a common multiple of $m$ and $n$. Our earlier proof about the least common multiple then tells us that as $(a-b)$ is a common multiple of $m$ and $n$, it is also a common multiple of their least common multiple.

$$ \operatorname{LCM}(m,n)\mid (a-b) \iff a \equiv b ;(\bmod{\operatorname{LCM(}m,n)}) $$

What is the $\operatorname{LCM}$ of two coprime integers?

$$ \operatorname{LCM}(a, b) = \frac{ab}{\gcd(a,b)} $$

From Wikipedia. As $m$ and $n$ are coprime $\gcd(m,n) = 1$.

$$ a \equiv b ;(\bmod{\operatorname{LCM(}m,n)}) = a \equiv b ;(\bmod m*n) $$

Putting this all together, if $a \equiv b ;(\bmod{m})$ and $a \equiv b ;(\bmod{n} )$, for coprime integers $a$ and $b$, $a \equiv b ; (\bmod{mn})$.

Footnotes

1. For the remainder of this essay I use the notation $a,b\mid L$ to denote "both $a$ and $b$ divide $L$". ↩