|
这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维。至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料。 素数是这样的整数
素数是以数的这样一种整除性为特征的，也就是说，它们是用只能被1和它们自身整除这种性质定义的。所以，素数应该具有的与它们所整除的数有关联的特殊性质并不是一目了然的。因此，下述与素数相关的论断既是很重要的，又是非显而易见的。关于素数的下述事实是重要的，但并非显而易见。 断言. 令p是素数，假设p整除乘积ab，则p整除a或p整除b(或者p既整除a也整除b) 证明 已知p整除乘积ab。如果p整除a，则证明已完成，所以可假设p不整除a。现在考虑gcd(p, a)等于什么。既然它整除p，它就是1或p，它也整除a，由于已假设p不整除a，所以gcd(p, a)不是p。因此gcd(p, a)必等于1。 应用p与a的线性方程定理。线性方程定理指出可以求方程 px + ay = 1 的整数解x与y。 (注意运用事实gcd(p, a)=1。)现在，方程两边同乘以b得 pbx + aby = b. 显然，p整除pbx。由于p整除ab,，p也整除aby。故p整除和pba + aby，从而p整除b。这就完成了断言的证明。 断言指出，如果素数整除乘积ab，则它必整除其中一个因数。注意这是素数的特殊性质，对合数则不成立，例如，6整除乘积15·14，但是6既不整除15也不整除14。不难将断言推广到超出两个因数的乘积的情形。 定理(素数整除性质) 假设素数p整除乘积 证明 如果p整除 得出p必整除 现在已知p整除 每个人都“知道”正整数可以恰好用一种方法分解成素数的乘积。 定理(算术基本定理) 每个整数
证明 算术基本定理实际上包含两个断言. 断言1 数n可以以某种方式分解成素数乘积. 断言2 仅有一种这样的因数分解(除因数重排外). 从断言1开始，我们准备给出归纳证明。首先证明n=2的断言，然后证明n=3的断言，n=4的断言，等等。我们开始观察2=2,，3=3与4=22，所以，这些数的每一个可表示成素数的乘积。这就证明了n=2,3,4的断言1。下面假设我们已证明了对于直到N的每个数n断言1成立，这意味着我们已证明了每个数n<N可分解成素数的乘积。现在验证N+1时的结论成立。 有两种可能性。首先，N+1已是素数，此时它本身已分解成素数。其次，N+1是合数，这表明它可分解成
将这两个乘积乘起来得
所以,N+1可分解成素数的乘积。这说明对N+1断言1成立。 总结一下，我们已证明如果对所有小于等于N的数断言1成立，则N+1时断言1也成立。 下面证明断言2。这个断言也有归纳证明,但我们直接证明它，假设能将n分解成两种形式的素数乘积，即
需要证明当重排因数次序后分解是相同的。首先观察 现在从等式两边消去
简要重述相同的论证，可以消去
继续这个过程直到所有的 我们已证明:如果
其中所有
这就完成了仅有一种表示方法将n表示成素数乘积的证明。 算术基本定理说明每个整数 如果n相当小(例如n=180)，可用检查法分解n，
如果n比较大(例如n=9105293)，求因数分解会更困难。一种方法是用素数2,3,5,7, 11,…试除n直到得到一个因数为止。对于n=9105293，经过试除后，得到了完全素因数分解
如果n本身不是素数，则必有整除n的素数 要将n表示成素数乘积，用小于等于 虽然这是一个效率非常低的过程，但对适当大的数，比如说不超过10位的数，在计算机上可以工作得很好。对于像 这就产生了下述两个紧密相关的问题: 问题1 如何分辨已知数n是素数还是合数? 问题2 如果n是合数，如何将它分解成素数的乘积? 虽然看起来似乎这两个问题相同，事实表明问题1要比问题2容易回答，这些问题将在另外的文章中予以讨论。 总结，
|
|
|
