来自潘承洞、潘承彪《初等数论》，有删改。
一、定义
定义 1（同余）设 \(m\ne 0\)。若 \(m\mid a-b\)，即 \(a-b=km\)，则称 \(m\) 为模，\(a\) 同余于 \(b\) 模 \(m\) 以及 \(b\) 是 \(a\) 对模 \(m\) 的剩余，记作
\[a\equiv b\pmod m(1) \]否则，则称 \(a\) 不同余于 \(b\) 模 \(m\)，\(b\) 不是 \(a\) 模 \(m\) 的剩余，记作
\[a\not\equiv b\pmod m \]关系式 \((1)\) 称为模 \(m\) 的同余式，或简称同余式。
由于 \(m\mid a-b\) 等价于 \(-m\mid a-b\)，所以同余式 \((1)\) 等价于
因此，我们总可以假定 \(m\ge 1\)。在同余式 \((1)\) 中，若 \(0\le b<m\)，则称 \(b\) 是 \(a\) 对模 \(m\) 的最小非负剩余；若 \(1\le b\le m\)，则称 \(b\) 是 \(a\) 对模 \(m\) 的最小正剩余。
对于给定的数 \(b\) 和模 \(m\)，所有同余于 \(b\) 模 \(m\) 的数就是算术数列
\[b+km,k=0,\pm1,\pm2,… \]二、判定条件
定理 1 \(a\) 同余于 \(b\) 模 \(m\) 的充分必要条件是 \(a\) 和 \(b\) 被 \(m\) 除后所得的最小非负余数相等。
证明：我们有 \(a-b=(q_1-q_2)m+(r_1-r_2)\)，所以 \(m\mid a-b\) 的充分必要条件是 \(m\mid r_1-r_2\)，由此及 \(0\le |r_1-r_2|<m\) 即得 \(r_1=r_2\)，证毕。
三、用处/优势
“同余”就是代表“余数相同”，它可以在数论中有效代替带余除法
\[a=km+b(2) \]如果 \((2)\) 成立，那么对于任意整系数多项式 \(f(x)\) 都有 \(m\mid f(a)\Leftrightarrow m\mid f(b)\)，使得我们在讨论问题时可以避开 \(k\)，突出 \(a\) 和其余数 \(b\) 在讨论被 \(m\) 整除的问题中两者起相同的作用。
四、性质
由基本的整除性质以及带余除法可得：
性质 \(\mathrm{I}\) 同余是一种等价关系，即有
\[a\equiv a\pmod m \]\[a\equiv b\pmod m\Leftrightarrow b\equiv a\pmod m \]\[a\equiv b\pmod m,b\equiv c\pmod m\Rightarrow a\equiv c\pmod m \]性质 \(\mathrm{II}\) 同余式可以相加，即若有
\[a\equiv b\pmod m,c\equiv d\pmod m(3) \]则有
\[a+c\equiv b+d\pmod m \]性质 \(\mathrm{III}\) 同余式可以相乘，即若 \((3)\) 成立，则有
\[ac\equiv bd\pmod m \]由性质 \(\mathrm{I}\)，性质 \(\mathrm{II}\)，性质 \(\mathrm{III}\) 可以推出：
性质 \(\mathrm{IV}\) 设 \(f(x)\) 和 \(g(x)\) 是两个 \(n\) 次的整系数多项式，并且
\[\forall i\in[0,n],a_i\equiv b_i\pmod m(4) \]那么，若
\[a\equiv b\pmod m \]则
\[f(a)\equiv g(b)\pmod m(5) \]定义 2 设 \(f(x)\) 和 \(g(x)\) 是两个 \(n\) 次的整系数多项式，并且满足 \((4)\)，那么称多项式 \(f(x)\) 同余于多项式 \(g(x)\) 模 \(m\)，记做
\[f(x)_{=}^{=}g(x)\pmod m(6) \]（其实这里的四条杠应该是均匀的，但是我打不出来）。
当满足式 \((5)\) 时，称多项式 \(f(x)\) 等价于多项式 \(g(x)\) 模 \(m\)，式 \((5)\) 为模 \(m\) 的恒等同余式。
注意 \((5)\) 不一定能推出 \((4)\)，比如 \(\forall x\in Z\)，多项式
但是其 \(x^m\) 次项系数为 \(1\)，模 \(m\) 不余 \(0\)。
下面是一些涉及模数的性质。
性质 \(\mathrm{V}\) 设 \(d\ge 1,d\mid m\)，那么，若同余式 \((1)\) 成立，则
\[a\equiv b\pmod d \]性质 \(\mathrm{VI}\) 设 \(d\ne 0\)，那么，若同余式 \((1)\) 成立，则
\[da\equiv db\pmod {|d|m} \]注意同余式两边不能直接相约，比如 \(6\times 3\equiv 6\times 8\pmod {10}\)，但是 \(3\not\equiv 8\pmod {10}\)。
性质 \(\mathrm{VII}\) 同余式
\[ca\equiv cb\pmod m(7) \]等价于
\[a\equiv b\pmod {\frac{m}{(c,m)}} \]即同余式两边可以同时约去 \(c\)。
证明：同余式 \((7)\) 即 \(m\mid c(a-b)\)，这等价于
由于 \(\big(\frac{m}{(c,m)},\frac{c}{(c,m)}\big)=1\)，所以上式等价于
\[\frac{m}{(c,m)}\mid a-b \]证毕
性质 \(\mathrm{VIII}\) 若 \(m\ge 1,(a,m)=1\)，则存在 \(c\) 使得
\[ca\equiv 1\pmod m(8) \]我们把 \(c\) 称为 \(a\) 对模 \(m\) 的逆，记做 \(a^{-1}\pmod m\) 或 \(a^{-1}\)。
证明
容易知道，\(a^{-1}\) 不唯一，但是 \(a^{-1}\bmod m\) 唯一。此外，易知
性质 \(\mathrm{IX}\) 同余式组
\[\forall j\in[1,k],a\equiv b\pmod {m_j} \]同时成立的充分必要条件是
\[a\equiv b\pmod {[m_1,m_2,…,m_k]} \] 标签：定义,mathrm,pmod,mid,笔记,同余,同余式,性质,equiv From： https://www.cnblogs.com/qwq-qaq-tat/p/17403315.html