初等数论

---

# 定义

完全剩余系

---

既约剩余系

---

多项式的根

---

群

1. 封闭性：对于任意 $a, b \in G$，运算结果 $a \cdot b$ 也属于 $G$。
2. 结合律：对于任意 $a, b, c \in G$，有 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$。
3. 单位元：存在一个唯一元素 $e \in G$，使得对于任意 $a \in G$，有 $a \cdot e = e \cdot a = a$。
4. 逆元：对于任意 $a \in G$，存在一个唯一元素 $b \in G$，使得 $a \cdot b = b \cdot a = e$。这个 $b$ 记为 $a^{-1}$。

• 所有整数 $\mathbb{Z}$ 在加法下构成一个群。单位元是 $0$，元素 $a$ 的逆元是 $-a$。
• 所有非零实数 $\mathbb{R} \setminus \{0\}$ 在乘法下构成一个群。单位元是 $1$，元素 $a$ 的逆元是 $1/a$。

阿贝尔群（交换群）

5. 交换律：对于任意 $a, b \in G$，有 $a \cdot b = b \cdot a$。

有限群

---

# 定理

Theorem.1 费马小定理

$$a^{p-1}\equiv 1\pmod p,p\in Prime,(a,p)=1$$

关于 $ac\equiv bc\pmod m$，是否能约去 $c$ 的问题。能约去 $c$ 当且仅当 $(m,c)=1$。

其相当于 $m|c(a-b)$，显然若 $(c,m)\ne 1$，只能推出 $\frac mc |(a,b)$ 即 $a\equiv b\pmod {\frac mc}$。不能推出 $m|(a,b)$。

---

Theorem.2 欧拉定理

$$a^{\varphi(m)}\equiv 1\pmod m,(a,m)=1$$

欧拉定理的实质是拉格朗日定理的推论：一个有限群的任意元素的阶都整除该群的阶。

模 $m$ 的既约剩余系是一个有限阿贝尔群。其群的阶，即群大小为 $\varphi(m)$，拉格朗日定理指出对于群中元素 $a$，$\delta_m(a)|\varphi (m)$。其中 $(a,m)=1$。

---

Theorem.3 威尔逊定理

$$p\in Prime\Leftrightarrow(p-1)!+1 \equiv 0\pmod p$$

• 正定理证明：

引理：令 $f(x),g(x)$ 是整系数 $n$ 次多项式，其根分别为 $f_1\dots f_n$ 和 $g_1\dots g_n$。

若 $[x^n]f(x)= [x^n]g(x)$ 那么 $f(x)=g(x)$。因式分解 $f,g$ 即可，不作严谨证明。

• 逆定理证明：

---

Theorem.4 中国剩余定理

$$\left\{ \begin{matrix} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \vdots\\ x\equiv a_n\pmod {m_n}\\ \end{matrix} \right.\\ M=\prod_{i=1}^n m_i ,M_i=\frac{M}{m_i},t_i\equiv M_i^{-1}\pmod {m_i}\\ x=(\sum_{i=1}^n a_it_iM_i)\bmod M$$

---