数论知识补充

数论基础补充

整除性

• 整除

设整数 $a, b, m$ ，如果有 $a = bm$ ，我们说 $b$ 被 $a$ 整除，用符号 $b|a$ 表示。

• 除法

设任意正整数 $n$ ，任意非负整数 $a$ ，如果用 $n$ 除 $a$ ，我们得到一个整数商 $q$ 和一个整数余数 $r$ ，他们服从下面的关系： $a = qn + r \quad 0 \le r \lt n; q = [a/n]$

• 模运算

根据上面除法的定义，我们有 $a \mod n = r$

• 模算数运算

1. $[(a \mod n) + (b \mod n)] \mod n = (a + b) \mod n$
2. $[(a \mod n) - (b \mod n)] \mod n = (a - b) \mod n$
3. $[(a \mod n) \times (b \mod n)] \mod n = (a \times b) \mod n$

• 模运算性质

1. 如果 $n|(a-b)$ ，那么 $a \equiv b \quad (\mod n)$
2. $a \equiv b (\mod n)$ 隐含 $b \equiv a (\mod n)$
3. $a \equiv b (\mod n), b \equiv c (\mod n)$ 隐含 $a \equiv c (\mod n)$

• 最大公因数

存在正整数 $c$ ，整数 $a, b$ ，有

1. $c|a，c|b$
2. 对任意 $k|a, k|b$ 都有 $c \le k$

我们说 $c$ 是 $a, b$ 的最大公因数，用 $\gcd(a, b)$ 表示

求最大公因数的算法

• 欧几里得算法
• 扩展的欧几里得算法

欧几里得算法（辗转相除法）

$\gcd(a, b) = \gcd(b, a \mod b) = \gcd(b, c) = \gcd(c, b \mod c)$ 循环下去知道两个数有一个是 $0$ . 其中 $c = a \mod c$

扩展的欧几里得算法

根据图示计算过程求得 $\gcd(a, b) = r_n = ax_n + by_n$ 。

群、环和域

群

定义了一个二元运算集合，使用 $G$ 或 $\{G, \cdot\}$ 表示。 一个序偶 $(a, b)$ 通过运算生成 $G$ 的元素 $(a \cdot b)$ 满足以下公理：

1. 封闭性：如果 $a, b$ 都属于 $G$ ，则 $a\cdot b$ 也属于 $G$.
2. 结合律：对于 $G$ 中的任意元素 $a, b$ 有 $a \cdot (b \cdot c) = (a \cdot b) \cdot c$.
3. 单位元：在 $G$ 中存在元素 $e$ 使得 $e \cdot a = a \cdot e = a$
4. 逆元：对于 $G$ 中任意元素 $a$ ，$G$ 中都存在 $a'$ 使得 $a \cdot a' = a' \cdot a = e$.
5. 交换律（可选）：如果 $G$ 中任意元素 $a,b$ ，都有 $a \cdot b = b \cdot a$ 成立。

如果一个群满足交换律，那么就叫做交换群。

例子 加法运算下的整数集合是交换群。乘法运算下的非零实数集合是一个交换群。

群的阶等于群中元素的个数，群中元素有限叫做有限群，无限的叫无限群；

循环群

在群中，我们定义幂为重复运用群中的运算，如加法群中： $a^3 = a + a + a$ ， $a^{-3} = (a')^3 = (-a) + (-a) + (-a)$。其中 $a'$ 是 $a$ 的逆元。 如果一个群中的元素都是通过一个固定的元素 $a \in G$ 的幂 $a^k$( $k$ 为整数) 生成的，那么这个群 $G$ 叫做循环群。我们说元素 $a$ 生成了群 $G$ ，或者说 $a$ 是群 $G$ 的生成元。循环群是交换群，有可能是有限群或无限群。

整数加法群是一个无限循环群。生成元是 $1$ 。他的每个元素 $n$ 都是 $1$ 的 $n$ 次幂。

环

环是有两个二元运算组成的集合，记为 $R$ 或 ${R, +, \times}$ ，这两个运算称为加法和乘法

中国剩余定理