一算术间题一、算术问题算木基本定理每个大于1的正整数均可惟一地写为素数的乘积，大数学家高斯（Gauss1777-1855)曾说：“数学是科学的王后，而数论则是数学的王后，”这句话虽然流露出高斯对数论的过分偏爱，但也说明了数论在数学家们心目中的崇高地位.事实上，从古希腊的欧几里得（Euclid，公元前330_前275）开始，儿千年来许多数学家都对数论产生过浓厚的兴趣，并进行了大量深刻的研究.时至今日，尽管数学已经发展成为一门内容庞大、应用广泛的学科，但还有很多在叙述上简明易懂的关于正整数的问题仍未得到完全解决，这真令人感到不可思议特别是其中的一些数论问题（如哥德巴赫猜想）几乎是家喻户晓，儿百年来它们像谜一样吸引着数学家以及无数的数学爱好者，在正整数或正整数的理论中，有一类称为素数的数扮演着非常重要的角色.事实上，素数在整数理论中的地位就像元素在化学中或基本粒子在物理学中的地位一样.我们知道，素数是指那些大于1的，且除了1和它自身外再没有其他因子的正整数.例如，2，3.5.7，11，13，等等.如果个正整数具有除了自身和1以外的其他因子，则称为合数.这样，可以把所有的正整数分成三类：1，素数与合数.素数的重要性首先表现在数的乘法分解方面.因为每个大于1的正整数α，如果本身不是素数，则存在不等于a和1的因子b，1
数学的100个基本问题此时可令a=bc,其中b.c都大于1.如果b(或c)不是素数的话，则重复这种分解过程，又可分解出b=b,b2（或c=cic2），显然a>b>b>1（或a>c>c>1).这个分解过程不能无限地重复下去，换句话说，有限步后就可以把分解成一些素数的乘积我们得到的结论是：每个大于1的正整数均可写成若干素数的乘积.从这个意义上讲，素数是构成正整数的基本元素.因此，在整数理论中遇到的许多命题大多能归结为有关素数的研究，也就不足为奇了，算术基本定理的内容由两部分构成：1.分解的存在性，指的是每个大于1的正整数均可分解成一些素数的乘积；2.分解的惟一性，即不考虑诸素数的排列顺序的话，则把正整数分解成素数乘积的方式还是惟一的：例如，21的素数分解只有21=3×7和21=7×3，但本质上属于同一种分解.算术基本定理是整数理论中最为基本的一个命题，也是许多其他命题的逻辑支撑点和出发点.上面已经证明了分解的存在性部分，其惟一性部分看起来似乎是显而易见的，但要严格地证明它却绝非易事，虽然它的证明较为初等，却需要精细的推理过程，充分反映了数学这门学科所特有的思维风格先介绍公元前300年的欧几里得在其巨著《几何原本》中所给的证明.下面只考虑正整数.如果d既是α的一个因子，又是b的一个因子，则称d为a和b的一个公因子.在a和b的所有公因子中的最大者称为最大公因子，记为（α，6）.欧几里得发明了一种“镶转相除法”去求两个正整数的最大公因子，从此导出了一个十分重要的结论：如果d是a和b的最大公因子，则存在整数x和y满足d=ax+by.这个结论从现代的观点也是非常基本的，如果读者熟悉近世代数的话，它相当于说全体整数构成的集合Z不仅是一个环，而是一个主理想整环，现在当然不会使用这个近代的结论，但要从欧几里得发现的这个最大公因子的表示公式出发去证
一算术间题明素数的一个基本性质：设p为素数，如果p整除两个正整数6和b的乘积，则p必整除其一,即p整除a或者p整除b.事实上，如果p不整除a，则p和a的最大公因子不是p，但p为素数，表明p和α的最大公因子只能为1.根据上述欧几里得导出的结论，存在整数x和y使得1=px+ay.两边用b去乘，有b=bpx+bay.因为等式右边的两项分别能被p整除，从而等式左边的b也能被p整除.由此即证所述结论，有了以上的准备工作，就可以证明算术基本定理中的惟一性部分了.设大于1的正整数n有两种素数分解n=P1P2"p,=q192""要证明的是r=s，且适当排列顺序后，可使每个pi=gi.事实上，反复应用上述关于素数的整除性质，从p：整除n=91929.可知Pi整除某个qj.但q;也是素数，只有pi=qj.重新对诸q:的足标编号，不妨设p1=91.此时在n的两个素数分解式中消去p1即得p2""P,=92""9..重复论证上述过程又得到p2=92.同理可知p3=93，，,=由此得出=且1P2，"，,恰为q1,92，，9s的一个排列，惟一性得证，当然，不使用辗转相除法也能直接证明算术基本定理，下面再介绍一个具有现代风格的证明，它比欧几里得的上述证明既简短又巧妙，我们的目标仍然是证明算术基本定理中雄一性部分，假设存在一个正整数n能以两种不同的方式分解为素数的乘积，则不妨选取几是这类数中最小的一个，如果据此能得到一个矛盾，则表明这样的正整数并不存在，亦即每个正整数都能以惟一的方式写成素数之积，从而就反证了算术基本定理成立.现在令(1)n=P1P2""P,=q1q2"""q为两种不同的素数分解，其中的p：和q;均为素数.经过适当的排列，不妨假设P≤P2≤≤Pr，91≤2≤"≤9.3
数学的100个基本问题显然p不能等于q1，否则的话，在等式(1)的两边同时约去第一个因子得到(2)P2P3"p,=q293*""qs这是一个比n小的正整数，而且从（1）为两种不同的素数分解可知(2)也如此，但这与n的最小选择相矛盾.所以p1≠q1，不妨设Pi<q1,此时令n=n-（p192939.），则n为正整数.现在把等式（1)中n的两种表示法分别代人到n中得到n'=(pip2"p.)-(pi92""q.)(3)=p(p2P3""p,-q2"*q);n'=(q1q2""g.)-(pi92""gs)(4)=(q1-pi)(q293q).因为n是比n小的正整数，根据n的选取可知n具有惟一的素数分解.所以从(3)推出pl是n一个素因子，再由(4)可知pi是91-p，或者是q2939,的素因子.注意到每个素数q,都比p1大，这表明p;只能是q1-p,的素因子.于是存在正整数m使得q1=P1=pim，但从此又可推出p，整除41，最后的这个矛盾就证明了算术基本定理的正确性.100中国剩余问题贴今有物不知其数，三三数之剩二，五五数之刺三，七七数之剩二，问物几何？这是我国古代数学名著《孙子算经》下卷中的第26题，即著名的“物不知数“问题，通常也称为“孙子问题”虽然《孙子算经》一书的作者与成书年代已难以精确地考证，但其中的“物不知数”问题千百年来在数学界甚至在民间广泛流传，被国际数学界誉为中国剩余定理.该问题相当于说求一个正整数x，使得x被3去除余数为2，被5去除余数为3，而被7去除余数为2.从问题的类型上看，它属于初等数论中的一次同余方程组的求解问题.为此，先介绍同4
算术问题余的概念.设a，b均为整数且b￥0,如果a是6的整数倍，即存在整数m使得a=mb，则称b整除a，也称b是a的一个因子.对任意整数c而言，如果b整除a-c,亦即a除以b所得的余数等于c除以b所得的余数，则称a和c模b同余，记为amc(modb).值得一提的是，同余的概念和符号是有“数学家之王”美称的德国数学家高斯在其24岁出版的划时代巨著《算术研究》中首先引进的.使用同余的符号，物不知数问题就转化为下述同余方程组的求解问题：（x=2（mod3)x3(mod5)x=2(mod7)不难看出，上述同余方程组的解并不惟一，因为如果x是一个解，则×+3×5×7×k=×+105k也是该同余方程组的一个解，其中的k可以取任意整数.事实上，从3，5，7两两互素（指没有大于1的公因数）可知上述同余方程组的任意两个解相差一个105的倍数.所以，一且求出“最小正整数解”xo，则每个解均可表示为x=xo+105k.如何求出上述同余方程组的一个解呢？我们的祖先聪明地把问题转化为以下三个非常特殊的同余方程组的求解：[a=1(mod3)(b=0(mod3)[c=0(mod3)a=0(mod5)b=1(mod5)c=0(mod5)a=0(mod7)(bm0(mod7)c=1(mod7)显然，如果求出了a，b，c的一组值，则2a+36+2c就是原同余方程组的一个解，再把这一个解除以105,则相应的余数即为所求的最小正整数解5