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，都可以唯一地表示为有限个素数的乘积（不计素因数的排列顺序）

数学表达为：对于任意$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$)

所以数论是现代互联网安全的基石！#

结语#

感谢您的游览！在此，也祝福你可以学好数学!而且考试天天能满分！面试也能直接通过！(^_^)