数论中正整数的因数个数（数论之因数分解与算术基本定理）

这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料，今天小编就来聊一聊关于数论中正整数的因数个数?接下来我们就一起去研究一下吧!

数论中正整数的因数个数

这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维。至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料。

素数是这样的整数，它的(正)因数仅有1与p。不是素数的整数叫做合数。例如，

素数	2,3,5,7,11,13,17,19,23,29,31,…
合数	4,6,8,9,10,12,14,15,16,18,20,...

素数是以数的这样一种整除性为特征的，也就是说，它们是用只能被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必整除的结论。换句话说，应用与的断言。我们已知pl整除ab,所以如果p不整除a，则断言表明p必整除b。

现在已知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是合数，这表明它可分解成，同时，已知对断言1成立，这是因为它们都小于等于N。从而与可分解成素数的乘积，即

将这两个乘积乘起来得

所以,N 1可分解成素数的乘积。这说明对N 1断言1成立。

总结一下，我们已证明如果对所有小于等于N的数断言1成立，则N 1时断言1也成立。

下面证明断言2。这个断言也有归纳证明,但我们直接证明它，假设能将n分解成两种形式的素数乘积，即

需要证明当重排因数次序后分解是相同的。首先观察，所以。本章前面已证的素数整除性质告诉我们必整除中的(至少)一个。所以如果重排这些可以使得。但是也是素数，因而它的因数仅是1与，因此必得。

现在从等式两边消去得等式

简要重述相同的论证，可以消去(等于)得到新的等式

继续这个过程直到所有的或所有的被消去。但是如果所有的被消去，则等式的左边等于1，所以右边没有任何。类似地，如果都被消去则必然被消去。 的个数一定等于的个数。

我们已证明:如果

其中所有与都是素数，则r=s。重排使得

这就完成了仅有一种表示方法将n表示成素数乘积的证明。

算术基本定理说明每个整数可表示成素数乘积。接下来的问题就是，如何把一个整数表示成素数乘积。

如果n相当小(例如n=180)，可用检查法分解n，

如果n比较大(例如n=9105293)，求因数分解会更困难。一种方法是用素数2,3,5,7, 11,…试除n直到得到一个因数为止。对于n=9105293，经过试除后，得到了完全素因数分解

如果n本身不是素数，则必有整除n的素数。要知道为什么成立，可以观察如果p是整除n的最小素数，则n=pm, ，从而，两边取平方根得。这就给出了将任何整数n表示成素数乘积的下述十分简单明了的方法：

要将n表示成素数乘积，用小于等于的海个数(或正好每个素数)2,3,...试除它，如果没有求得整除n的整数，则n本身是素数，否则求得的第一个因数是素数p，分解得n=pm，然后对m重复这个过程。

虽然这是一个效率非常低的过程，但对适当大的数，比如说不超过10位的数，在计算机上可以工作得很好。对于像这样的数，将非常耗时，以至于计算机无法在可接受时间内解决问题。

这就产生了下述两个紧密相关的问题:

问题1 如何分辨已知数n是素数还是合数?

问题2 如果n是合数，如何将它分解成素数的乘积?

虽然看起来似乎这两个问题相同，事实表明问题1要比问题2容易回答，这些问题将在另外的文章中予以讨论。

总结，

1. 素数合数是对自然数的一种分类，用的是整除性，这样，大数可以用小数表示，且合数可以归结到素数问题
2. 算术基本定理的证明，把问题分裂成两个子问题分别解决，并使用了归纳法。

,