2.算数基本定理

2.1 质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

质数有无穷个

考虑反证，如果质数有限，我们设这个集合为 \(S\) 。我们求出 \((\prod_{p \in S} p)+1\) ，那么对于任何一个 \(p \in S\) ，都不满足 \(b|(\prod_{p \in S} p)+1\) 。那么 \((\prod_{p \in S} p)+1\) 就是我们构造出的全新质数。但是 \((\prod_{p \in S} p)+1 \notin S\) ，与我们的假设违背。所以质数有无穷个。

若 \(2^{n}-1\) 为质数，则 \(n\) 为质数

我们考虑一个前置命题：对于 \(a,b>1\) ， \(2^a-1|2^{ab}-1\)。

这个命题等价于 \(2^{ab} \equiv 1 (\bmod 2^{a}-1)\) 。因为 \(2^a \equiv 1 (\bmod 2^{a}-1)\) , 那么 \(\prod_{i=1}^{b}2^{a} \equiv \prod_{i=1}^{b}1 (\bmod 2^a-1)\) 。这整理可得 \(2^{ab} \equiv 1 (\bmod 2^a-1)\) ， \(2^{ab}-1 \equiv 0(\bmod 2^a-1)\) 。

若 \(n\) 不是质数，那么 \(\exists a,b>1\) 满足 \(ab=n\) 。由于 \(2^a-1|2^{ab}-1,2^{b}-1|2^{ab}-1\) ，所以 \(2^n-1\) 是合数与命题违背，所以 \(n\) 是质数。