质数、合数
| 质数 | |
|---|---|
| 术语名称 | 质数 |
| 英语名称 | prime number |
| 别名 | 素数 |
| 合数 | |
|---|---|
| 术语名称 | 合数 |
| 英语名称 | composite number |
只考虑正整数范围， 质数/素数(prime)指仅有两个正因数的正整数（此时，这两个因数一定是 1 和自身，即两个平凡因数）， 合数(composite number)指有至少三个正因数的正整数（或者说，存在 1 和自身以外的因数，即非平凡因数）。 正整数被分为 1，质数和合数三类。
也对应定义在整数上，此时不考虑符号的话和上面的对应。
| 不可约数 | |
|---|---|
| 术语名称 | 不可约数 |
| 英语名称 | irreducible number |
| 可约数 | |
|---|---|
| 术语名称 | 可约数 |
| 英语名称 | reducible number |
类似地，不可约数(irreducible number)指不能分解成两个非单位（±1）的乘积，可约数(reducible number)指能分解成两个非单位（±1）的乘积。 在讨论整数环时，不可约数就是质数，可约数就是合数。但如果讨论的数环是其他结构的，这个不一定成立。
定义
对正整数，根据其正因数的数量分为三类：
- 有一个正因数。这一分类只有 1 ，仅有 1 一个正因数。（单位(unit)）
- 有两个正因数。这类正整数被称为质数/素数(prime number)，仅有 1 和自身两个正因数。
- 有两个以上正因数。这类正整数被称为合数(composite number)，除 1 和自身外有非平凡的正因数。
注：也定义为是否能被 1 和自身以外的数整除。
注：也定义在整数集上，此时负数和其绝对值一同处理， ±1 都是单位。
注：在通常的整数集中，质数和合数也分别可以称为不可约数和可约数。广义上这两对名词对应环上的素元非素元、可约元不可约元，但对整数集是相同的，不做区别。
注：由于习惯因素，在数论领域，通常使用“素数”一词，其他领域则更常使用“质数”一词。
通常使用字母 p 表示任意质数，多个质数则带下标。
性质
| 质因数 | |
|---|---|
| 术语名称 | 质因数 |
| 英语名称 | prime factor |
| 别名 | 素因数, 质因子, 素因子 |
- 质数有无限个。反证法将所有的整数相乘加一可知这个数一定大于最大质数且也是个质数。
- 参见质数计数函数。
- 每个大于 1 的整数都有质数的因数，称为质因数。
- 且每个大于 1 的整数总能被分解为质因数乘积形式，且忽略顺序时唯一。
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |
琐事
命名
“质数”或“素数”的“质”和“素”是拉丁语 prīmus 或英语 prime “首要的”或“基本的”、“单一的”、“不可再分的”的对应，两个词均取“基本”的含义[1]。“质”可参考“本质”、“质子”（而且这个词的翻译是用“质”对应同义的希腊源词根 proto- ）中的。“素”也是使用了“基本”的含义，并在同期翻译出了“元素”、“色素”等词。一说“素”的使用是这一词义的回流或激活[2]。曾经两岸都有使用两个词并行的情况，目前港台及日韩以素数的说法为主。