同余

日本学年参考：数学A

学习内容

本节学习将除以某个数后余数相同的整数进行归类与计算的同余方法。该工具常用于快速求解大数高次幂的余数及证明数论性质。在学习前，建议先掌握整数除法与余数的基本性质。

要点

这是同余式的定义，表示整数 $a$ 和 $b$ 除以 $m$ 后的余数相同。只要余数相同，两者的差 $a - b$ 就必然是 $m$ 的整数倍。

a \equiv b \pmod{m} \iff a - b = km \quad (k \in \mathbb{Z})

这是同余式加减乘的重要性质。只要模数 $m$ 相同，同余式之间就可以像普通等式一样进行加法、减法和乘法运算。

a \equiv b, \; c \equiv d \implies a \pm c \equiv b \pm d, \; ac \equiv bd \pmod{m}

用于计算大数乘方除以 $m$ 后的余数。两边同时取相同的正整数 $n$ 次方后依然同余，因此可先将底数 $a$ 替换为较小的余数 $b$ 再计算。

a \equiv b \implies a^n \equiv b^n \pmod{m}

请选择要练习的题组。