数论笔记5-同余理论

温馨提示: 这一篇的性质非常多 (不过很多性质都比较简单)

1. 同余

若 \(m|a-b\), 称 \(a,b\) 模 \(m\) 同余, \(b\) 是 \(a\) 对模 \(m\) 的剩余, 记作 \(a\equiv b\pmod m\). 反之记作 \(a\not\equiv b\pmod m\).
容易发现负数模和正数模是等价的, 所以我们只讨论 \(m\geqslant1\) 的情况.
接下来我们给出一些关于同余的基本性质.

1. 设 \(a=q_1m+r_1,b=q_2m+r_2,0\leqslant r_1,r_2<m\). 则\(a\equiv b\pmod m\Lrarr r_1=r_2\). (同余的字面意义)
2. 同余是一种等价关系.
3. \(a\equiv b\pmod m,c\equiv d\pmod m\Rarr a+c\equiv b+d\pmod m\) (可加性)
4. \(a\equiv b\pmod m,c\equiv d\pmod m\Rarr ac\equiv bd\pmod m\) (可乘性)
5. \(a\equiv b\pmod m, d\geqslant1,d|m\Rarr a\equiv b\pmod d\)
6. \(a\equiv b\pmod m\Lrarr da\equiv db\pmod {|d|m}(d\ne 0)\)
7. \(ca\equiv cb\pmod m\Lrarr a\equiv b\pmod {m/(c,m)}\)
8. \(m\geqslant1,(a,m)=1\Rarr\exist c,ca\equiv 1\pmod m\) (逆元)
9. \(a\equiv b\pmod {m_j}, 1\leqslant j\leqslant k\Lrarr a\equiv b\pmod {[m_1,\cdots,m_k]}\)

性质 1 到性质 7 都是很容易证明的. 性质 9 由 2.3.1 显然.
性质 2 的等价关系的意思就是满足自反性, 对称性, 传递性, 即:

• \(a\equiv a\pmod m\)
• \(a\equiv b\pmod m\Lrarr b\equiv a\pmod m\)
• \(a\equiv b\pmod m, b\equiv c\pmod m\Rarr a\equiv c\pmod m\)

性质 8 实际上就是二元一次不定方程, 也不难证明. 这里我们记 \(c\) 为 \(a^{-1}\), 称为 \(a\) 对模 \(m\) 的逆元. 容易发现逆元有性质 \((a^{-1},m)=1\) 和 \((a^{-1})^{-1}\equiv a\pmod m\).

对于多项式我们也有同余的概念.
设多项式 \(f(x)=\sum_{j=0}^na_jx^j,g(x)=\sum_{j=0}^nb_jx^j\), 若满足 \(a_j\equiv b_j\pmod m\ (0\leqslant j\leqslant n)\), 则有 \(a\equiv b\pmod m\Rarr f(x)\equiv g(x)\pmod m\) (显然), 此时我们称这两个多项式模 \(m\) 同余, 记作 \(f(x)≣g(x)\pmod m\). 若只满足 \(\forall x\in\mathbb{Z},f(x)\equiv g(x)\pmod m\), 称这两个多项式模 \(m\) 等价.
需要注意的是模 \(m\) 等价并不意味着模 \(m\) 同余, 比如取 \(f(x)=\prod_{i=0}^{m-1}(x-i), g(x)\equiv0\).

2. 同余类和剩余系

之前说过同余就是一种等价关系. 由此我们得出同余类 (剩余类) 的概念.
对全体整数进行划分, 使得两个数在同一个集合里当且仅当它们模 \(m\) 同余. 我们将这样划分出的每个集合称为一个模 \(m\) 的同余类, 记作 \(r\bmod m\), 其中 \(r\) 是它所属的同余类的一个代表元素.
有简单性质:

1. \(r\bmod m=\{r+km|k\in\mathbb{Z}\}\), 由此我们也记 \(r\bmod m=r+m\mathbb{Z}\).
2. \(r\bmod m=s\bmod m\Lrarr r\equiv s\pmod m\)
3. \(r\bmod m=s\bmod m\) 和 \((r\bmod m)\cap(s\bmod m)=\varnothing\) 两者必居其一.
4. 模 \(m\) 恰有 \(m\) 个不同的同余类 \(0\bmod m,\cdots,(m-1)\bmod m\), 它们构成的集合称为 \(\mathbb{Z}_m\).
5. 任意 \(m+1\) 个数中必有两数模 \(m\) 同余.
6. 存在 \(m\) 个数两两对 \(m\) 不同余.
7. 设 \(a_1\in r\bmod m,a_2\in r\bmod m\), 则 \((a_1,m)=(a_2,m)\).

但我们其实并不需要完整研究每个同余类. 我们只需要从每个同余类里面选出一个元素即可. 这就构成了完全剩余系.
更严格的定义: 一组数 \(y_1,\cdots, y_m\) 被称为模 \(m\) 的完全剩余系, 当且仅当对任意整数 \(a\), 有且只有一个数 \(y_j\) 满足 \(a\equiv y_j\pmod m\).

3. 欧拉函数, 威尔逊定理