质数――高级概念
质数（又称素数）
质数只能被 1 或自己整除，并且一定要是大于 1 的整数。
例子：2、3、5、7、11 等等。
孪生质数
孪生质数就是相差2的质数对（连续两个都是质数的奇数）。
例子：(3,5)、(5,7)、(11,13) ……
是否有无穷多的孪生质数目前还是个未解的问题。
互质
公约数只是 1 或 −1 的两个整数（它们的最大公因数是 1 或 −1）
例子：15 和 28 是互质的，因为 15 的因数(1,3,5,15) 与 28 的因数 (1,2,4,7,14,28) 除了 1 之外是没有相同的。
梅森质数
形如 2n-1 的质数，在这种情况下，n 也是质数。
3、7、31、127 等都是梅森质数
当 n 为质数数时，2n-1 不一定是质数。例如，2047（=211-1）不是质数，虽然 11 是质数。2047 可以被 23 和 89 整除。
完全数
如果一个正整数等于它的个别真因数之和，这个数就叫完全数。一个数的真因数是不等于它自己的因数。
例子：6（真因数：1、2、3）是完全数，因为 1+2+3=6。
例子：28（真因数：1、2、4、7、14）也是完全数，因为 1+2+4+7+14=28。
欧几里得证明了如果 2n-1 是个梅森质数，2n-1(2n-1) 便是个偶完全数。我们现在称这些数为欧几里得数。欧拉证明了所有偶完全数都可以用这个格式及一个正质数 n 来表达。例如，把 3、7 和 31 代入公式的 2n-1 项就得到 6、28 和 496 这三个完全数。
这个表列出了从 n=1 到 13 的结果，包括了前首五个完全数：
| n | 2n-1 | 2n-1(2n-1) | 是完全数？ | 注 |
|---|---|---|---|---|
| 1 | 1 | 1 | 否 | n 不是质数 |
| 2 | 3 | 6 | 是 | n 是质数，2n-1 是质数 |
| 3 | 7 | 28 | 是 | n 是质数，2n-1 是质数 |
| 4 | 15 | 120 | 否 | n 不是质数 |
| 5 | 31 | 496 | 是 | n 是质数，2n-1 是质数 |
| 6 | 63 | 2016 | 否 | n 不是质数 |
| 7 | 127 | 8128 | 是 | n 是质数，2n-1 是质数 |
| 8 到 10 | …… | …… | 否 | 不是质数 |
| 11 | 2047 | 2096128 | 否 | n 是质数，但 2n-1 不是质数 |
| 12 | 4095 | 8386560 | 否 | n 不是质数 |
| 13 | 8191 | 33550336 | 是 | n 是质数，2n-1 是质数 |
是否有无穷多的偶完全数是个还未解决的问题。
盈数（又称丰数，过剩数）
任何小于它所有个别真因数的和的正整数。
例子：12 是盈数，因为它的个别真因数是 1、2、3、4 和 6，而这些数的和是 16。
亏数（又称作缺数）
任何大于它所有个别真因数的和的正整数。
质数是亏数，因为它只有一个真因数：1。
所有可以写成 2n 的数都是亏数。
例子：32（=25）是亏数，因为它个别真因数的和是 31(1+2+4+8+16）。
并且，当 p 为质数以及 n 为正整数时， pn 便是亏数。
例子：35=243。
243 的真因数是 81、27、9、3 和 1。
这些因数的和是 121，小于 243。
同样，56=15625，15625 的因数是 1、5、25、125、625 和 3125。
这些数的和是 3906，小于 15625。
相亲数（又称亲和数、友爱数、友好数）
两个数，彼此的个别真因数的和与另一方相等。
例子：220 和 284 是相亲数，因为：
- 220 的因数（不算本身）是 1、2、4、5、10、11、20、22、44、55、110。
这些因数的和 = 284 - 284 的因数（不算本身）是 1、2、4、71、142。
这些因数的和 = 220。
威尔逊定理
当且仅当 n 为质数时，则 (n-1)!+1 是 n 的倍数：
(n-1)! ≡ -1 (mod n)
欧几里得的无穷质数证明
这个证明基于：若有最大的指数，则会导致谬误。
把质数顺序排列并以数字标记：P1 = 2、P2 = 3、P3 = 5 等等。假设只有 n个质数，最大的质数就是 Pn。我们现在把所有的质数相乘，然后把积加一，称这个数为 Q：
Q = (P1 × P2 × P3 × P4... × Pn) + 1
如果我们用 Q 除以任何的质数，余数都会是一，所以 Q 不能被任何的质数整除。
但是，我们知道只有两种正整数：质数或可以分解为质数的积的数。所以 Q 必然是质数或者可以被大于 Pn 的质数整除。
无论是哪个情形，都有大于 Pn 的质数。假设 Pn 是最大的质数与此矛盾，所以假设必然是错误的。就是说，没有最大的质数。
哥德巴赫猜想
任一大于或等于 6 的偶数都可以表示成二个奇质数的和。
哥德巴赫也猜想所有的奇数都是三个奇质数的和：维诺格拉多夫定理证明了，除了可能有穷个数的奇数以外，这对于所有的质数都是成立的。