初等数论以及欧几里德定理的证明

本文主要是介绍初等数论以及欧几里德定理的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欧几里德定理(无限质数定理)

质数的个数是无限的吗？还是说存在一个最大的质数，比它大的任何数字都可以表示为已有质数的乘积？首先提出这个问题的正式欧几里得本人，他以一种简单而优雅的方式证明了质数有无穷多个，所以并不存在所谓的”最大质数”。为了验证这个命题，我们暂且假设质数的个数是有限的，并用字母N来达标已知最大的质数。现在我们将所有质数相乘，最后再加1，数学表达式如下：

$(1\times 2\times3\times5\times 7\times 11\times 13\times \cdots \times N)+1$

这个式子得出的结果当然比所谓的“最大质数” N大得多，但是这个数显然不能被任何一个质数（最大到N为止）整除，因为它是用上面这个式子构建出来的。根据这个数学式，我们可以清晰的看到，无论用哪个质数去除它，最后必然得到余数1.因此，我们得到这个数字要么是个质数，要么能被一个大于N的质数整除，无论哪个结果都必将推翻我们最初的假设，即N是最大的质数。

这种证明方法叫做归谬法，它是数学家最爱的工具之一。

基于以上推理，我们可以进行这种构造验证一下，看每次构造出来的数字是否都是质数。

从最初的两个质数开始构造：

$p_1=2, p_2=3$

根据上面的反证法，已知 $p_1, p_2, \cdots, p_n$ ,构造出 $p_{n+1}$ 方法为：

$p_{n+1}=p_{1}p_{2}\cdots p_{n}+1$

所以，

$\\ p_1=2\\p_2=3\\p_3=p_1p_2+1 = 7 \\ p_4=p_1p_2p_3+1 = 43 \\ p_5 = p_1p_2p_3p_4+1 =1807 \\ p_6 = p_1p_2p_3p_4p_5+1 =3263443 \\ ...$

2,3,7,43是素数，但1807虽然处以2，3，7，43都余1，但是它不是素数，1807=13*139，但是没关系，我们又发现了新的素数13，可以继续运算。

实际上，2*3*7*43*13+1=23479，也不是素数，它等于53*443，没关系，无论你得到的结果是不是素数，都会发现新的素数。素数是无穷多个。

定理证明的基础-算术基本定理（注意不是代数基本定理）

定理证明的基础是算术基本定理，描述为，任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，当代入1时候这种分解是无限的，去掉1时分解则是唯一的。

为了保证算术基本定理为1，1不能是质数，因为6=2*3，如果1是质数了，那么6=2*3*1，或者6=2*3*1*1。。。，所以，规定1不是质数。

算术基本定理的证明

描述：设整数 a ≥ 2 , 那么 a 一定可表示为素数的乘积，即

$a=p_1 p_2 p_3 \cdots p_s$

其中 $p_j (0\leq j\leq s)$ 是素数. （分解式中的素数可以相同）.

证明：反证法. 假设结论不成立，则存在正整数 ≥ 2，它不能表示为素数的乘积. 设所有这种正整数组成的集合为 T，所以，根据假设，它是非空的,并且素数不能在这个集合中，因为任何素数都可以表示为1和它自身的积，不满足集合条件，所以集合中的元素一定是非素数，而非素数的数一定是合数，设 $n_0$ 是T中的最小者，由于 T 中元素都不是素数,故 $n_0$ 是合数，所以必有：

$n_0=n_1n_2, 2\leq n_1,n_2 <n_0$

由 $n_0$ 的最小性得到， $n_1,n_2$ 一定不再集合T中，所以都可表为素数的乘积：

$n_1=p_{11}p_{12} \cdots p_{1s}, n_2=p_{21}p_{22} \cdots p_{2r}$

这样，就把 $n_0$ 表示为素数的乘积了：

$n_0=n_1n_2=p_{11}p_{12} \cdots p_{1s}p_{21}p_{22} \cdots p_{2r}$

这与假设矛盾. 证毕.

素数定理（区别代数基本定理，算术基本定理。。。:()

质数的个数公式π(n)是不减函数。且素数的分布个数接近于x/ln (x)，这是素数定理,高斯提出来的，表示为：

$\pi(x)\sim \frac{x}{ln(x)}$

设x≥1，以π(x)表示不超过x的素数的个数，当x→∞时，π(x)～x/ln(x)。这个函数和真实的π(x)有些误差。

素性测试

常用的算法，在2到sqrt(n)之间任取一个数,如果n能被整除则不是素数，否则就是素数：

#include<stdio.h>
#include <math.h>
int main(void)
{int i,j,n;printf("Please input numbers: ");scanf("%d",&n);j=(int)sqrt(n);for(i=2;i<=j;i++){if(n%i==0){break;}}if(j<i){printf("%d is prime!\n",n);}else{printf("%d is not prime!\n",n);}return 0;
}

此程序的理论依据如下：实际上是第一条定义的逆否命题，如果没有一个2到sqrt(a)的数字能够整除（条件更强，不仅仅限定素数）a，那么a就不可能是合数了。