Instantly share code, notes, and snippets.

# 0xekez/LCM and Congruence.md

Last active February 25, 2023 07:20
Show Gist options
• Save 0xekez/079ab6d51023ea4f2edfcba50e60f5d3 to your computer and use it in GitHub Desktop.

# 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$ 1. 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$".