整除

定义

整除

设 如果 使得 那么就说 可被 整除，记作 且称 是 的倍数 是 的约数（或除数，因数），若 不能被 整除就记作

素数

设整数 如果它除了显然约数 外没有其他约数，那么 就称为不可约数，也叫做素数，若有 且 不是不可约数，则称 为含数。当 时由于 和 必同为不可约数或合数，所以不做特殊说明的话，不可约数（素数）指正的。

定理

1. 
2. 且
3. 且 则 有
4. 设 那么
5. 且
6. 设 那么
7. 设整数 是它的全体约数。那么 也是它的全体约数。也就是说，当 遍历 的全体约数时 也遍历 的全体约数。此外，若 则当 遍历 的全体正约数时 也遍历 的全体正约数。
8. 是合数的充要条件是
9. 设 且 是不可约数，若 则
10. 若 是合数，则必有不可约数
11. 设整数 那么 一定可表示为不可约数的乘积（包括 本身是不可约数），即 其中 是不可约数。
12. 不可约数有无穷多个
13. 设全体素数按大小排列的序列是我们有及这里 表示以 为底的对数且 表示不超过 的素数个数。

推论

设整数 则

• 若 是合数，则必有不可约数
• 若 可表示为 则必有不可约数

证明