同余式及其表示方法是由万能的高斯最先引入的, 定义为 $a$ 和 $b$ 模 $m$ 同余当且仅当 $m \mid (a - b)$. 记做 $a \equiv b\ (mod\ m)$.

最基本的, 同余式满足交换律和传递性.

同余式保持加法和减法:
若 $a\equiv b\ (mod\ m)$ 那么 $a \pm c\equiv b \pm c\ (mod\ m)$

乘法:
若 $a1 \equiv b1\ (mod\ m)$ 且 $a2 \equiv b2\ (mod\ m)$, 那么 $a1 a2 \equiv b1 b2\ (mod\ m)$

在乘法中, 模 $m$ 的倍数相当于零元.
当模 $m$ 为质数 $p$, 而 $k$ 不是零元时, 某定理说一定有乘法逆元 $k^{-1}\epsilon \{1, 2, \cdots, p-1\}$ 的存在, 使:
$k \cdot k^{-1} \equiv 1\ (mod\ p)$

所以当模 $m$ 为质数 $p$, 而 $k$ 不是零元时, $a k \equiv b k\ (mod\ p)$ 两边可以乘以 $k^{-1}$ 消去 $k$ 得到 $a\equiv b\ (mod\ p)$.

若要得到除法, 想要把一边的 $k$ 除到另一边成为 $k^{-1}$ 就得知道乘法逆元的计算方法, 根据费马小定理:
若 $p$ 是质数且 $k$ 不是 $p$ 的倍数. 则有 $k^{p-1} \equiv 1\ (mod\ p)$.
所以 $k^{-1} = k^{p-2}$.

把上面的乘法逆元和除法推广到模为正整数 $n$. 这时和 $n$ 不互质的数相当于零元. 非零元根据某定理亦一定有乘法逆元 $k^{-1}\epsilon \{1, 2, \cdots, p-1\}$ 存在.

同理 $k$ 不是零元时, $a k \equiv b k\ (mod\ n)$ 可消去得到 $a\equiv b\ (mod\ n)$.

欧拉定理是费马小定理的推广:
$n$ 是正整数且 $k$ 互质于 $n$. 则有 $k^{\phi(n)} \equiv 1\ (mod\ n)$.

所以乘法逆元 $k^{-1} = k^{\phi(n)-1}$.

updated at 2013-1-25:

Two ways to influence the modulus:

• Divide all three side by a common divisor:
  $6\equiv 36\ (mod\ 10) \Leftrightarrow 3\equiv 18\ (mod\ 5)$.


• Reduce modulus alone but this is not reversible:
  $7\equiv 13\ (mod\ 6) \Rightarrow 7\equiv 13\ (mod\ 3)$.

updated at 2013-3-31:

$a \equiv b\mod{lcm(p,q)} \quad \Leftrightarrow \quad \begin{equation}\begin{cases} a \equiv b\mod{p} \\\\ a \equiv b\mod{q} \end{cases}\end{equation}$

$a \equiv b\mod{p\ q} \quad \Rightarrow \quad \begin{equation}\begin{cases} a \equiv b\mod{p} \\\\ a \equiv b\mod{q} \end{cases}\end{equation}$ (右边比左边解多)

$$ a^d \equiv 1 \mod {m} $$

设 $\delta$ 为使上成立的最小的 $d$，若 $\delta = \phi(m)$ 则称 $a$ 是模 $m$ 的原根。

对所有 $d$ 有 $\delta \mid d$。$a^0, a^1, \dots, a^{\delta-1}$ 模 $m$ 两两不同余。构成模 $m$ 乘法群（剩余系），阶为 $\delta$。

$ x^a \equiv 1 \mod {p} $ 互不同余的解的个数为 $\gcd(a,\ p-1)$。