2.1 整除定义#

如果整数 $a$ 除以整数 $b$ ($b \neq 0$) 的余数为 0，我们就说 $b$ 整除 $a$，或者 $a$ 能被 $b$ 整除。 记作： $b \mid a$ 这意味着存在一个整数 $k$，使得 $a = bk$。

2.2 基本性质#

• 传递性： 若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$。
• 线性组合： 若 $a \mid b$ 且 $a \mid c$，则对于任意整数 $x, y$，有 $a \mid (bx + cy)$。

3.1 素数#

一个大于1的整数，如果除了1和它本身以外没有其他正因数，则称之为素数(也可以叫质数)。否则，称为合数。

• 前几个素数：2, 3, 5, 7, 11, 13, 17, 19…
• 注意: 1既不是素数也不是合数。

3.2 算术基本定理#

这是数论中最重要的定理之一。它指出： 任何一个大于1的整数都可以唯一地分解为素数的乘积。

数学表达为：对于任意 $n > 1$ ，存在唯一的素数 $p_1 < p_2 < \dots < p_k$ 和正整数 $a_1, a_2, \dots, a_k$，使得： $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

示例：

$12 = 2^2 \times 3$

$600 = 2^3 \times 3^1 \times 5^2$

这种分解是唯一的(不考虑顺序)。

4.1 定义#

• 最大公约数: 两个或多个整数共有约数中最大的一个。记作 $\gcd(a, b)$ 或 $(a, b)$。
• 最小公倍数: 两个或多个整数共有倍数中最小的正整数。记作 $\operatorname{lcm}(a, b)$ 或 $[a, b]$。

4.2 欧几里得算法#

也称为“辗转相除法”，是求 GCD 最古老且高效的算法。 核心原理：$\gcd(a, b) = \gcd(b, a \bmod b)$。

算法步骤示例：求 $\gcd(1071, 462)$

1. $1071 = 462 \times 2 + 147$ (余数 147)

2. $462 = 147 \times 3 + 21$ (余数 21)

3. $147 = 21 \times 7 + 0$ (余数 0)

当余数为 0 时，除数即为最大公约数。

结果： $\gcd(1071, 462) = 21$

4.3 裴蜀定理#

对于不全为 0 的整数 $a, b$，存在整数 $x, y$ 使得： $ax + by = \gcd(a, b)$ 这是求解线性同余方程的基础。

5. 同余运算#

同余是数论的“时钟算术”。

6.1 费马小定理#

如果 $p$ 是素数，且 $a$ 是不可被 $p$ 整除的整数，那么： $a^{p-1} \equiv 1 \pmod p$ 这个定理在素数测试和公钥加密中非常重要。

6.2 欧拉函数与欧拉定理#

• 欧拉函数 $\phi(n)$: 表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。
• 欧拉定理: 若 $\gcd(a, n) = 1$，则： $a^{\phi(n)} \equiv 1 \pmod n$ (注:费马小定理是欧拉定理在$n$为素数时的特例，因为对于素数$p$，$\phi(p) = p-1$)

所以数论不再只是数学家的口头禅，而是现代互联网安全的基石。#

结语#

感谢您的游览！在此，也祝福你可以学好数学!