初等数论基础：素数与算术基本定理

本节介绍素数、合数等概念，在此基础上建立算术基本定理并考虑这一定理的一些应用.首先给出素数的概念.

定义1.4.1　设a∈Z，a＞1.若其正因数只有1及其本身，称a是素数，否则，称其为合数.

注1.4.2　素数也称为质数或不可约数；素数均为正整数；全体正整数分为1、素数和合数三类.

例1.4.3　设n是正整数.则（n+1）！+2，（n+1）！+3，…，（n+1）！+n+1是n个连续的合数.

定理1.4.4　合数a的除1以外的最小正因数是素数且不超过

证明　设a的除1以外的最小正因数是p且a=pq.若p为合数，则存在p1，p2∈Z，使得p=p1p2且1＜p1，p2＜p.这说明p1是a的除1以外的正因数且p1＜p，矛盾.故p是素数.注意到a是合数，有q≠1.由p的最小性知p≤q.故a=pq≥p2.即p≤证毕.

推论1.4.5　设a是大于1的整数.若不超过的素数均不能整除a，则a是素数.

例1.4.6　找出不超过100的全部素数.

解　注意到不超过的素数为2，3，5，7，据推论1.4.5，不超过100的合数必能被2，3，5，7中之一整除.于是2，3，5，7再加上2到100之间不能被2，3，5，7中任何一个整除的数就是所求的全部素数.经验证知这些素数是2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97.解毕.

定理1.4.7　　　（欧几里得）素数有无限个.

证明　设p1，p2，…，pn是所有素数，则a=p1p2…pn+1是合数.据定理1.4.4知a的除1以外的最小正因数p是素数.无妨设p=p1.则p1=p|a=p1p2…pn+1.这导致p1|1，矛盾.证毕.

命题1.4.8　设a，b∈Z，p是素数，则（a，p）=1或p|a.另外，若p|ab，则p|a或p|b.

证明　由（a，p）|p及p是素数知（a，p）=1或（a，p）=p.当（a，p）=p时，由（a，p）|a知p|a.故该命题之前一结论成立.设p|ab.若，则必有（p，a）=1.据命题1.2.9（4）知p|b.证毕.

推论1.4.9　若ai∈Z，i=1，2，…，n，p是素数且p|a1a2…an，则p至少整除a1，a2，…，an中的一个.

定理1.4.10（算术基本定理）　任何大于1的整数a均可唯一地表示为a=p1p2…pn，其中p1，p2，…，pn是素数且p1≤p2≤…≤pn.

证明　对a用数学归纳法.当a=2时，结论显然成立.现设结论对大于1小于a的一切整数成立.下证结论对整数a也成立.若a是素数，则结论显然成立；若a是合数，则a=bc，其中b，c均为大于1小于a的整数.由归纳假设，b，c均可以写成一些素数的乘积，于是，a就可以写成若干素数的乘积.将这些素数按由小到大排列即可得a=p1p2…pn，其中p1，p2，…，pn是素数且p1≤p2≤…≤pn.若还有a=q1q2…qm，其中q1，q2，…，qm是素数且q1≤q2≤…≤qm，则

p1p2…pn=q1q2…qm.

这说明p1|q1q2…qm.由推论1.4.9知存在qj使得p1|qj.对偶的，存在pi使得q1|pi.由于p1，q1，pi，qj均为素数，故p1=qj，q1=pi.注意到p1≤pi=q1≤qj=p1，有p1=q1，从而

p2…pn=q2…qm.

类似讨论可得p2=q2.依次进行下去便知n=m且pi=qi，i=1，2，…，n.证毕.

推论1.4.11　任何大于1的整数a均可唯一地表示为

其中p1，p2，…，pn是素数，αi是正整数且p1＜p2＜…＜pn，i=1，2，…，n.该表达式称为a的标准分解式.此时，p1，p2，…，pn是a的全部素因数.

例1.4.12　正整数51480的标准分解式是51480=23×32×5×11×13.

例1.4.13　4n+3型素数有无穷多个.(www.xing528.com)

证明　设p1=3，p2，…，pt是所有4n+3型素数，则a=4p2…pt+3是合数.我们断言，a无4n+3型素因数.否则，设q是a的4n+3型素因数.若q=3，则由q|a知3|4p2…pt.据命题1.2.9（4）及（3，4）=1知3|p2…pt，再据推论1.4.9知3整除某个pi（i≥2）.这导致pi=3，矛盾.若q=pj，j≥2.则由q|a知q|3，进而有q=pj=3，矛盾.于是，据定理1.4.10知a为若干4n+1型素数的乘积，但4n+1型素数的乘积为4n+1型数，与a是4n+3型数矛盾.证毕.

命题1.4.14　设大于1的整数a的标准分解式为，则a的所有正因数为

证明　显然集合F中的元素均为a的正因数.反之，设d|a.若d=1，则显然有d∈F.下设d≠1.先确定d的素因数.设p是d的素因数.则p也是a的素因数，从而p就是p1，p2，…，pn中的某一个.据推论1.4.11知d有如下表达式由d|a知0≤εi≤αi，i=1，2，…，n.这表明d∈F.证毕.

推论1.4.15　设a，b是大于1的整数，其中

pi是素数，αi，βj是非负整数，i，j=1，2，…，n且p1＜p2＜…＜pn.则

其中γi=min｛αi，βi｝，δi=max｛αi，βi｝，i=1，2，…，n.

例1.4.16　由51480=23×32×5×70×11×13和41580=22×33×5×7×11×130知

（51480，41580）=22×32×5×70×11×130=1980，

［51480，41580］=23×33×5×7×11×13=1081080.

注1.4.17　需要指出的是，推论1.4.15所阐述的求最大公因数和最小公倍数的方法不能代替辗转相除法，因为求一个正整数的标准分解式至今没有统一的方法.

本节最后介绍有趣的费马数［这是以法国著名数学家费马（Fermat，1601—1665）之名命名的一类重要的整数］，借此可得到“素数无限个”这一重要结论的另一证明.

定义1.4.18　设m是非负整数.称为费马数.前几个费马数为

F0=3，F1=5，F2=17，F3=257，F4=65537，F5=641×6700417，

其中，最后一个等式是瑞士数学家欧拉（Euler，1707—1783）于1732年指出的.

诸费马数之间有以下重要关系.

定理1.4.19　关于任意正整数n，有其中∏是连乘符号.

证明　对n用数学归纳法.由于F0=3=5-2=F1-2，故当n=1时结论成立.设结论对n=t时成立，即则当n=t+1时，有

这说明结论对n=t+1的情形也成立.由归纳法原理，命题对任意正整数n都成立.证毕.

推论1.4.20　不同的两个费马数互素，从而素数有无限个.

证明　设m，n是非负整数且m＜n，则据定理1.4.19知

Fn=F0F1…Fm-1FmFm+1…Fn-1+2=（F0F1…Fm-1Fm+1…Fn-1）Fm+2.

据命题1.2.5及费马数均为奇数这一事实，有（Fn，Fm）=（Fm，2）=1.故不同的两个费马数互素.设素数只有有限多个.据算术基本定理，每个费马数都有素因数.由于费马数有无穷个，从而必有两个费马数有公共的素因数，这与不同的两个费马数互素矛盾.故素数有无限个.证毕.

注1.4.21　需要指出的是，费马数因其几何上的特殊应用得到人们的高度关注.这是因为，高斯（Gauss，1777—1855）曾证明，若Fn是素数，则正Fn边形可尺规作图.一般的，正n边形可尺规作图当且仅当n=2αp1p2…ps，其中，α是非负整数，p1，p2，…，ps是两两互异的费马素数（具体可参见文献［15］）.另外，费马曾猜测，费马数均为素数.1732年，欧拉指出F5不是素数，从而否定了费马的猜想.事实上，到目前为止，人们知道的费马素数就只有F0，F1，F2，F3，F4这5个，但也无人能证明当m≥5时，Fm均为合数.