<< elementary_number_theory

Congruence

# Definition of Congruence

Given \(m\ge0\), for two integer \(a\) and \(b\), if \(m\mid(a-b)\), we say \(a\) and \(b\) are congruence modulo \(m\), notes as \(a\equiv b \pmod m\).

Usually the modulus \(m\ge2\). If \(m=0\), \(0~|~(a-b)\) if any only if \(a = b\). If \(m=1\), \(1~|~(a-b)\) is always true. Both cases are so trivial to discuss.

Congruence can be regarded as a generalization of parity (odd or even), parity is the congruence when \(m=2\).

# Properties of Modular Arithmetic

The operations on the congruence equation are named as modular arithmetic.

Remark. This proof seems like a memory hack more than a formal proof, since the last digit of \(a\) based on \(m\) is exactly the value of \(a \bmod m\), which seems like a circular reasoning.

Noticed that the form of division is special: the calcellation of factor in both sides will cause the change of modulo. \[ ac \equiv bc \pmod m ~~~~\Rightarrow~~~~ a\equiv b \left( \textrm {mod}\ {\cfrac{m}{\textrm{gcd(c, m)}}}\right) \]

The proof of division rule using the important property of divisibility Calcellation Law.