Congruence

discrete-math

Definition

Congruence

Two elements $a$ and $b$ are called congruent modulo $n$ if $m$ divides $b-a$:

$$a\equiv b(\mathrm{mod}m):⟺m\mid b-a$$

where $m$ is called modulus.

Inverse

Given a congruence relation as the following:

$$ac\equiv bc(\mathrm{mod}m)$$

Before one can divide by $c$, one needs to figure out whether $c^{-1}$ exists. This is the case if:

$$c\cdot c^{-1}=1⟺\gcd (c,m)=\pm 1$$

Common Factor

Given a congruence relation as the following, with $m=\tilde{m}c$:

$$ac\equiv bc(\mathrm{mod}m)$$

$ac$, $bc$ and $m$ are all multiples of $c$, which means that one can simplify the relation:

$$\begin{array}{rl}\exists k\in \mathbb{Z}ac& =bc+k\tilde{m}c\\ ⟺a& =b+k\tilde{m}\\ ⟺a& \equiv b(\mathrm{mod}\tilde{m})\end{array}$$