质数无穷性的证明

这篇文章作为博客里的第一篇NOTE,就写篇关于质数无穷性的证明的文章吧
首先我们先说说最广为人知又记录最早的欧几里得大神的《几何原本》中记录的证明吧
首先假设质数有限且全体质数集合(保持大小有序)为

A=\{p_1,p_2,p_3,...,p_{n-1},p_n\}



q=p_1 \times p_2 \times p_3 \times ... \times p_{n-1} \times p_n+1


q 必然比 p_n 大,且 q 必然不是质数,因为 p_n 已经是最大的质数了,既然 q 不是质数,那么集合 A 中必然存在 q 的质因子,我们设这个质因子是 p ,既然 p 在质数集合中,那么 p 必然能整除 q-1 ,又因为 pq 的质因子,那么 p 必然能整除 q ,由此推得 p 必然也能整除 q-(q-1) ,明显 p 并不可能整除1。所以“ p 存在 A 集合中”的前提就是错误的,故而得到 p 为质数,且不存在 A 集合中,所以包含全部质数的 A 集合不存在,故质数无穷:)