高中数学扩展/素数/定义表

HSME
内容
素数
模算术
问题和项目
问题集
项目
解决方案
习题解答
问题集解答
杂项
定义表
完整版
PDF 版本

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步的模算术 — 数学规划 — 马尔可夫链

关于定义表

以下提供的定义可能与章节中给出的定义略有不同。如果可能，请打印出以下定义以便于参考。

---

定义

合数

合数是指不为素数的整数。数字1不是合数。

互质数

如果两个数的最大公约数（GCD）等于1，则这两个数互质。

丢番图方程（线性）

形如 *ax* + *by* = *c* 的方程。其中 *a*、*b* 和 *c* 是整数常数，*x* 和 *y* 是未知整数。

因式分解

也可以拼写为 factorization。一个过程，找到自然数的素因数，并将该数表示为各个因数的乘积。

GCD（最大公约数）

*a* 和 *b* 的 GCD 是一个数字 *d*，使得 *d* 整除 *a* 且 *d* 整除 *b*；并且如果 *e* 整除 *a* 和 *b*，则 *e* ≤ *d*。

逆

在模 *m* 运算中，*a* 的逆是指满足以下条件的数字 *b*：

$ab\equiv 1{\pmod {m}}\!$

逆是唯一的。并非每个运算中的每个数字都有逆。

模运算

模 *m* 运算是在每个数字都用介于 0 和 m - 1 之间的数字表示的运算。例如，考虑模 7 运算，11 用 4 表示；-2 用 5 表示。我们说 11 等于 4 模 7；-2 等于 5 模 7。它在这里有更详细的解释。

素数

素数（或简称素数）是指只能被两个不同的数字（1 和它本身）整除的整数。因此，数字 1 不被视为素数。本章不考虑负数。

---

定理

中国剩余定理

在一个包含 *n* 个同余式的系统中

$x\equiv a_{1}{\pmod {m_{1}}}\,\!$

$x\equiv a_{2}{\pmod {m_{2}}}\,\!$

...

$x\equiv a_{n}{\pmod {m_{n}}}\,\!$

，解存在当且仅当对于 i 和 j 且 i ≠ j

GCD(m_i,m_j) 整除 (a_i - a_j)

逆的存在

在模 *m* 运算中，*a* 有逆当且仅当 GCD(*a*,*m*) = 1。

算术基本定理

任何整数（除了 1）都可以用唯一的方式表示为素数的乘积。

无穷多个素数

素数有无穷多个。