李兆華

(天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，天津300387)

素?cái)?shù)，早期譯為數(shù)根。數(shù)根一詞始見(jiàn)于《數(shù)理精蘊(yùn)》(1723)下編卷38。李善蘭(1811～1882)、偉烈亞力(A.Wylie，1818～1887)譯《幾何原本》后九卷(1857)沿用數(shù)根一詞，見(jiàn)該書(shū)卷7。中國(guó)傳統(tǒng)數(shù)學(xué)沒(méi)有給出素?cái)?shù)的概念。晚清的數(shù)學(xué)家比較關(guān)注素?cái)?shù)的研究并給出若干有意義的結(jié)果。其中，李善蘭《考數(shù)根法》(1872)與方士①方士，字梅蓀，湖北天門(mén)人，生卒年代不詳?！稊?shù)根叢草》卷首校算人名有門(mén)人周國(guó)柱等。李迪《中國(guó)算學(xué)書(shū)目匯編》載，“《南郡書(shū)院算學(xué)課藝》，(清)方梅蓀閱定，周國(guó)柱編次”，光緒二十六年刊本，未見(jiàn)傳本。南郡謂施南府，治今湖北恩施縣。王同愈(1856～1941)《栩緣日記》卷2光緒二十六年九月十六日記，“施南府縣來(lái)電云:方山長(zhǎng)士，有品無(wú)行，即復(fù)電?！蓖跏蠒r(shí)任湖北學(xué)政。見(jiàn)顧廷龍編《王同愈集》，上海古籍出版社，1998年?！稊?shù)根叢草》(1897)是晚清討論素?cái)?shù)判別法的兩部主要著作?！犊紨?shù)根法》［1］是國(guó)人論述素?cái)?shù)最早的工作。光緒二十二年(1896)夏，因門(mén)人請(qǐng)教《考數(shù)根法》，方士遂有《數(shù)根叢草》［2］之作。余經(jīng)華為之補(bǔ)草。

《考數(shù)根法》的主要結(jié)論可表述如下。設(shè)N，a是正整數(shù)，(N，a)=1。求得最小正整數(shù)d②《考數(shù)根法》共給出十八個(gè)例題，所得d不都是最小的。例如“準(zhǔn)根分級(jí)法”第四例，N=14209，a=2，求得d=6720。第五例，N=16637，a=2，求得d=8190。兩例中的d均非最小。參見(jiàn)下文。使得

d稱為“定次”。N為素?cái)?shù)的充分與必要條件是，d整除N-1，且kp+1不整除N。其中，k，p是正整數(shù)，p整除d。［3］顯然，該法的關(guān)鍵是求得d。《考數(shù)根法》給出四種求d的方法，即“屢乘求一法”、“天元求一法”、“小數(shù)回環(huán)法”及“準(zhǔn)根分級(jí)法”。［4］①嚴(yán)敦杰“中算家的素?cái)?shù)論”一文所引“準(zhǔn)根分級(jí)法”術(shù)文有誤。應(yīng)據(jù)《中西聞見(jiàn)錄》第4號(hào)原文改正。設(shè)(N，a)=1，N是素?cái)?shù)，則aN-1≡1(modN)。此即費(fèi)爾馬小定理(1640)。李善蘭上述結(jié)論的實(shí)質(zhì)是，將費(fèi)爾馬小定理中的必要條件加強(qiáng)，使成為充分與必要條件。這一結(jié)論說(shuō)明李善蘭對(duì)費(fèi)爾馬小定理的深刻認(rèn)識(shí)。至于求d四法，前二法較后二法為上?！靶?shù)回環(huán)法”，用的純循環(huán)小數(shù)的循環(huán)節(jié)長(zhǎng)度d判別N是否素?cái)?shù)，只是舉例說(shuō)明并未闡述理由。“準(zhǔn)根分級(jí)法”，用“超乘補(bǔ)乘”求d，當(dāng)不能求得d時(shí)又借助“天元求一法”另行計(jì)算，尚非完整的方法?！犊紨?shù)根法》具有重要價(jià)值，亦有不足之處。

《數(shù)根叢草》共給出20術(shù)，每術(shù)之后均有例題。術(shù)文與例題結(jié)合，說(shuō)明判別N是否素?cái)?shù)的方法。在這20術(shù)中，第6術(shù)、第10術(shù)與第11術(shù)的理論有誤;第12術(shù)與13術(shù)實(shí)用價(jià)值不大;②第12術(shù)可表述為，設(shè)N＞1是正整數(shù)，N為素?cái)?shù)的充分與必要條件是(N-1)!≡-1(mod N)。第13術(shù)據(jù)此用對(duì)數(shù)計(jì)算。計(jì)算量非常大。設(shè)N是一個(gè)3位數(shù)，則(N-1)!+1超過(guò)100位數(shù)。見(jiàn)李文林主編《王元論哥德巴赫猜想》，山東教育出版社，1999年，第108頁(yè)。第1術(shù)、第4術(shù)與第5術(shù)用最小素因數(shù)試除法，理由比較明顯，③若N＞1是合數(shù)，則N的最小素因數(shù)列出這些素因數(shù)逐一試除N。當(dāng)N很大時(shí)，滿足條件的素因數(shù)約為個(gè)。等等。除此之外，《數(shù)根叢草》比較重要的術(shù)文包括:第2術(shù)，第7至第9術(shù)，第14術(shù)，第17至第20術(shù)。此9術(shù)中，第14術(shù)與第19術(shù)，第18術(shù)分別是李善蘭“小數(shù)回環(huán)法”與“準(zhǔn)根分級(jí)法”的完善，其他6術(shù)是因數(shù)分解判別素?cái)?shù)法的運(yùn)用?！稊?shù)根叢草》的內(nèi)容選擇與文字表述不如《考數(shù)根法》精審，而初等數(shù)論的知識(shí)與方法超出《考數(shù)根法》者亦復(fù)不少。

關(guān)于《數(shù)根叢草》的討論并不多見(jiàn)，目前主要有“《數(shù)根叢草》研究”［5］一文。該文最早指出，第12術(shù)是威爾遜(J.Wilson，1741～1793)定理，④威爾遜定理:若p是素?cái)?shù)，則(p-1)!≡-1(mod p)。方氏第12術(shù)是一個(gè)充分與必要條件。在初等數(shù)論中，這是兩個(gè)定理。M.克萊因《古今數(shù)學(xué)思想》稱后者為威爾遜定理。見(jiàn)該書(shū)第2冊(cè)第367～368頁(yè)，上海科學(xué)技術(shù)出版社，1979年?！啊稊?shù)根叢草》研究”一文的稱謂同該書(shū)。本文沿用這一稱謂。并認(rèn)為方氏獨(dú)立得到這一定理;并且指出，第10術(shù)、第11術(shù)誤以為費(fèi)爾馬小定理的逆命題為真，重復(fù)了華蘅芳(1833～1902)的錯(cuò)誤;同時(shí)就第6術(shù)等若干術(shù)文給出解釋。這一工作使得《數(shù)根叢草》的內(nèi)容引起關(guān)注。就術(shù)文的解釋而言，該文尚有錯(cuò)誤和遺漏。本文基于《數(shù)根叢草》與《考數(shù)根法》的聯(lián)系，重點(diǎn)考察《數(shù)根叢草》第2術(shù)等9術(shù)的內(nèi)容，就其中因數(shù)分解判別素?cái)?shù)法的運(yùn)用、“小數(shù)回環(huán)法”與“準(zhǔn)根分級(jí)法”的完善等兩項(xiàng)工作的數(shù)學(xué)意義予以分析，補(bǔ)正以往解釋的某些錯(cuò)漏，從而說(shuō)明晚清數(shù)學(xué)家認(rèn)識(shí)與運(yùn)用素?cái)?shù)判別法的水準(zhǔn)。為敘述的方便，術(shù)文的順序作了調(diào)整，原有序號(hào)一并標(biāo)出。文中的例題除一例之外均選自《考數(shù)根法》與《數(shù)根叢草》。

1 因數(shù)分解判別素?cái)?shù)法之運(yùn)用

第7術(shù):

先取略大于本數(shù)之一個(gè)平方積，與本數(shù)相減，為余實(shí)。乃以所取之平方根倍之加一，以加余實(shí)，視其能否成方積。不成，又加倍平方根加三。不成，又加倍平方根加五。于是屢加，至適成一個(gè)正方積而止。乃以所成之方根為半較，加本數(shù)開(kāi)平方之根為半和，以和較相加減，即得大小乘數(shù)。如所加之?dāng)?shù)已近本數(shù)折半自乘之?dāng)?shù)，則不必求乘數(shù)，即知本數(shù)是數(shù)根。

記本數(shù)為N，取x使x2＞N，x2-N為余實(shí)。依次計(jì)算

由初等數(shù)論知，設(shè)N是奇數(shù)，a＞b，若

由式(1)求得x，y，即可求得因數(shù)a，b:

其中，x，y一奇一偶。若N是奇素?cái)?shù)，則N能且僅能表為

故式(1)中x的取值范圍是

在第7術(shù)中，因每步增加的值分別為2x+1，2(x+1)+1，2(x+2)+1，…，2(x+n-1)+1，故其演算采用以下兩例的格式較為簡(jiǎn)便。

判別N=1891是否素?cái)?shù)。

由x2-N=y2，即

可知，N=1891不是素?cái)?shù)。

判別N=31是否素?cái)?shù)。

由x2-N=y2，即由式(2)，可知，N=31是素?cái)?shù)。

第7術(shù)與費(fèi)爾馬因數(shù)分解判別素?cái)?shù)法(Fermat's factorization method)相同。［6］

第8術(shù)、第9術(shù)與第7術(shù)同義。第8術(shù)用

術(shù)文“如所加之平方根已大于本數(shù)，則知本數(shù)是數(shù)根?！彼又椒礁?2n)。由式(3)，準(zhǔn)確的表述當(dāng)為“如所加之平方根已等于本數(shù)減一，則本數(shù)是數(shù)根?！钡?術(shù)用

第6術(shù):

置本數(shù)加一開(kāi)平方。不盡，又加一個(gè)八開(kāi)之。不盡，又加二個(gè)八開(kāi)之。不盡，又加三個(gè)八開(kāi)之。于是屢加，至開(kāi)方適盡而止。乃以開(kāi)得之?dāng)?shù)為半和，所加之平方根為半較，和較相加減，即得大小兩乘數(shù)，則知本數(shù)必非數(shù)根。如果所加之平方根已與本數(shù)折半之?dāng)?shù)相近，而仍不能開(kāi)平方，或開(kāi)方之?dāng)?shù)等于本數(shù)加一折半之?dāng)?shù)，則知本數(shù)是數(shù)根。

本術(shù)有誤。記本數(shù)為N。若N不是素?cái)?shù)，依術(shù)當(dāng)有

事實(shí)上，這個(gè)等式不一定成立。由式(1)可知，x，y一奇一偶，即y可奇可偶。若規(guī)定y=2n+1，則N+(2n+1)2不一定是完全平方數(shù)。例如，N=221=17×13。若

則

解得x=15，(2n+1)=2。但(2n+1)是奇數(shù)。矛盾。因而，第6術(shù)是錯(cuò)誤術(shù)文。

［5］沒(méi)有指出這一錯(cuò)誤，反將第6術(shù)列為“獨(dú)創(chuàng)的素?cái)?shù)判別法”予以解釋和肯定。

第20術(shù):

置本數(shù)開(kāi)平方，不盡，余負(fù)實(shí)。以開(kāi)得之?dāng)?shù)為大方根。又以負(fù)實(shí)開(kāi)方為小方根，余正實(shí)。倍大方根加一，以減正實(shí)，余負(fù)實(shí)。倍小方根，除之為第一數(shù)，加于倍小方根內(nèi)，以乘第一數(shù)，與負(fù)實(shí)相加，余正實(shí)。倍大方根加三減之，余負(fù)實(shí)。倍小方根內(nèi)加倍第一數(shù)，除之為第二數(shù)，相加，以第二數(shù)乘之，與負(fù)實(shí)相加，余正實(shí)。又倍大方根加五減之，余負(fù)實(shí)。如是屢減屢加，至余實(shí)恰盡而止。如大方根已至本數(shù)六［二］①原文六分之一，誤。以第6術(shù)、第7術(shù)例此，當(dāng)作二分之一，蓋二與六行書(shū)字形相近而誤。分之一而仍不盡，則知本數(shù)是數(shù)根。如能恰盡，則以所加之大方根為半和，所加之小方根為半較，半和較相加減，即得大小乘數(shù)，則知本數(shù)非數(shù)根。合問(wèn)。

記本數(shù)為N，x為大方根，-ri為余負(fù)實(shí)，y為小方根，+si為余正實(shí)，i=0，1，2，…，n。依次計(jì)算

其中，

由此可得

在式(4)中，若rn=0，則

在式(5)中，若sn=0，則

可知，N不是素?cái)?shù)。

若rn≠0，當(dāng)時(shí)，由式(4)必有

若sn≠0，當(dāng)時(shí)，由式(5)必有

由式(2)，可知，N是素?cái)?shù)。

第20術(shù)與第7術(shù)同義，唯第7術(shù)的變?cè)莤，而第20術(shù)則為x，y。術(shù)文“如大方根已至本數(shù)六［二］分之一而仍不能盡，則知本數(shù)是數(shù)根”，乃約略之言。大方根即(x+n)。由式(3)，準(zhǔn)確的表述當(dāng)為“如大方根已至本數(shù)加一折半自乘，減本數(shù)開(kāi)方適盡，則知本數(shù)是數(shù)根”。

參考文獻(xiàn)［5］遺漏rn=0的情況。原文“已至本數(shù)六分之一”，于理不通，當(dāng)校而未校，結(jié)論“若……已近而sk+1≠0，……知N為數(shù)根(素?cái)?shù))”隨之而誤。

第17術(shù):

先取略近本數(shù)之一個(gè)方根。以除本數(shù)，得數(shù)與方根相減為根較。余負(fù)實(shí)若干置于下。任取一個(gè)奇數(shù)以加根較，①“根較”原文誤作“方較”。上文作“根較”，據(jù)改。仍與奇數(shù)相乘，得數(shù)以減負(fù)實(shí)，視其恰盡否。不盡，又以奇數(shù)減方根為法，除本數(shù)，如前求之，至屢求恰盡而止。即以其法為小乘數(shù)。如法已為三，而仍不能盡，則知本數(shù)是數(shù)根。

本條術(shù)文稍嫌簡(jiǎn)略，須結(jié)合例題方可了解術(shù)意。記本數(shù)為N，取x1為偶數(shù)以x1除N求得正整數(shù)稱為根較，ri稱為余實(shí)，i=1，2，3，…，n+1。余實(shí)可正可負(fù)，術(shù)文以余負(fù)實(shí)為例。依次計(jì)算

判別N=7081是否素?cái)?shù)。

原草如下。取x1=84，得y1=85，r1=-59。依次計(jì)算

而

可知，N=7081不是素?cái)?shù)。

依術(shù)文所說(shuō)，“任取一個(gè)奇數(shù)以加根較，仍與奇數(shù)相乘”，即上式7×［85-(84-7)］之中的奇數(shù)7為“任取”。例題演草所說(shuō)，“任于七十七之內(nèi)減一偶數(shù)四”，即上式4×［92-(77-4)］之中的偶數(shù)4為“任減”。奇數(shù)7與偶數(shù)4分別對(duì)應(yīng)上述k1=4，k2=2。這種“任取”具有偶然性。例如，將奇數(shù)7代之以9，偶數(shù)4不變，即k1=5，k2=2，則不能得到分解7081=73×97。為了避免“任取”，可令k1=k2=k3=…=kn=1。雖計(jì)算次數(shù)增加，但不致出現(xiàn)遺漏。仍用上例，逐步計(jì)算，所得結(jié)果相同，具體演算從略。

事實(shí)上，令k1+k2+k3+…+kn=k，式(6)變?yōu)?/p>

或即

可知，N不是素?cái)?shù)。若對(duì)任一k，［x1-(2k-1)］不整除rk+1，則N是素?cái)?shù)。

在上例中，x1=84，y1=85，取k=6，得7081=73 ×97。

第2術(shù):

記本數(shù)為N，①原文“巳”字對(duì)應(yīng)英文字母p。此處記作N以求上下文符號(hào)一致。以為平方之限，依次求得余數(shù)即

若am=ak，則自am+1起不再計(jì)算。此時(shí)，

可知，N不是素?cái)?shù)。

判別N=51是否素?cái)?shù)。

余數(shù)49重復(fù)出現(xiàn)。此時(shí)

可知，51不是素?cái)?shù)。

由初等數(shù)論知，設(shè)(N，a)=1，二次同余式

有解或無(wú)解。若式(8)有解，則a稱為模N的平方剩余。若式(8)無(wú)解，則a稱為模N的平方非剩余。當(dāng)N是奇素?cái)?shù)時(shí)，模N的簡(jiǎn)化剩余系中，平方剩余與平方非剩余的個(gè)數(shù)各為個(gè)。且個(gè)平方剩余分別與之中一數(shù)且僅與一數(shù)同余。［7］據(jù)此，將依次代入式(8)，求得余數(shù)此時(shí)，，且

當(dāng)N不是素?cái)?shù)時(shí)，設(shè)N=N1N2，N1，N2＞1 是奇素?cái)?shù)。將x=1，2，3，…，(N-1)依次代入式(8)，求得余數(shù)a1，a2，a3，…，aN-1，刪去(N，ai)≠1 的各數(shù)，滿足式(8)條件的余數(shù)共有

個(gè)。φ(N)是歐拉函數(shù)，表示模N簡(jiǎn)化剩余系中正整數(shù)的個(gè)數(shù)。由二次同余式解的定理知，此時(shí)式(8)有4個(gè)解。故式(8)的平方剩余只有

)個(gè)。又因

當(dāng)N=N1N2N3…Nk時(shí)，Ni＞1是奇素?cái)?shù)，有類似的結(jié)論。

數(shù)N的平方剩余不會(huì)重復(fù)出現(xiàn)，反之亦然。故當(dāng)平方剩余重復(fù)出現(xiàn)時(shí)，即可判定N不是素?cái)?shù)。

若am=ak，則由

將N分解為乘積形式。

用上述結(jié)論檢驗(yàn)原例N=51的分解過(guò)程如下。

等9個(gè)數(shù)時(shí)，a的值分別是

此時(shí)，(51，a)≠1，刪去之，還有如下16 式

在以上16式中，余數(shù)a均滿足條件(51，a)=1，余數(shù)的個(gè)數(shù)為

其中，平方剩余的個(gè)數(shù)為

每個(gè)平方剩余重復(fù)出現(xiàn)2次。分解N=51的方式共8種，分別是

由其中任一方式均可將N分解。例如，由(b)-(III)有

因而，只要平方剩余重復(fù)出現(xiàn)，即可據(jù)以分解N。以上例而言，只需式(a)出現(xiàn)即可，式(VII)以下無(wú)需計(jì)算。

該術(shù)運(yùn)用平方剩余概念作因數(shù)分解以判別N是否素?cái)?shù)，然而術(shù)文殊欠完整?！盁o(wú)相同之余數(shù)”的情形，該術(shù)未予說(shuō)明。此外，計(jì)算亦欠嚴(yán)謹(jǐn)。原例所給10個(gè)余數(shù)中，余數(shù)9，36，30當(dāng)刪而未刪。

參考文獻(xiàn)［5］稱該術(shù)“利用了這樣的事實(shí):模p的簡(jiǎn)化剩余系中，平方剩余與非平方剩余的個(gè)數(shù)各為由以上所述可見(jiàn)，該術(shù)只論N不是素?cái)?shù)的情形，并未利用所指的事實(shí)。引文亦須說(shuō)明，模p為奇素?cái)?shù)。否則，命題不真。此外，參考文獻(xiàn)［5］取x0“使其是相同數(shù)之剩余數(shù)，這樣就必有t2=x0，…”，似有誤文。

2 “小數(shù)回環(huán)法”與“準(zhǔn)根分級(jí)法”之完善

第19術(shù):

將本數(shù)之各倍一一列于右，另以一與本數(shù)之各倍兩兩相加，視其得若干次復(fù)變?yōu)橐?。乃以其次?shù)約本數(shù)，是否余一。否，則本數(shù)非數(shù)根。是，則即以其奇數(shù)倍之為遞加數(shù)，加一，除本數(shù)。不盡，又加一個(gè)遞加數(shù)，除之。如是屢加至得數(shù)小于法，仍不盡，則知本數(shù)是數(shù)根。

記本數(shù)為N，依次計(jì)算

其中，ki N是本數(shù)的各倍數(shù)，1≤ki≤9是正整數(shù)，Ai=ai1ai2ai3…aij是個(gè)位數(shù)aij≠0的正整數(shù)，i，j=1，2，3，…。當(dāng)Am=1 時(shí)，計(jì)算過(guò)程結(jié)束。此時(shí)，d=d1+d2+d3+ … +dm為所求的次數(shù)即定次。據(jù)此，用李善蘭的結(jié)論判別N是否素?cái)?shù)。

事實(shí)上，由上列各式可得，

又Am=1，故

即

因而，d=d1+d2+d3+…+dm為所求的定次。

求其第一個(gè)循環(huán)節(jié)的除法計(jì)算過(guò)程。例如，

由此除法算式逆推可得

故d=1+1+1+5=8。第19術(shù)即這一計(jì)算過(guò)程的一般表述?；癁榧冄h(huán)小數(shù)的充分與必要條件是(N，10)=1。只有N滿足這一條件必能化為純循環(huán)小數(shù)，從而得d。當(dāng)N是奇素?cái)?shù)時(shí)的循環(huán)節(jié)長(zhǎng)度等于N-1，或m，且m整除N-1。因而，可以借助循環(huán)節(jié)長(zhǎng)度以判別N是否素?cái)?shù)。

第14術(shù):

置本數(shù)減一，以十約之。不盡，加若干個(gè)本數(shù)約之為第一數(shù)，又將第一數(shù)以十約之。不盡，內(nèi)加若干本數(shù)約之為第二數(shù)，如是屢約，至第幾數(shù)始為一，或等于本數(shù)減一。乃計(jì)所約若干次。如末數(shù)為一，則將次數(shù)倍之為方指數(shù)。如末數(shù)為本數(shù)減一，即以次數(shù)為方指數(shù)。于是，以方指數(shù)為遞加數(shù)，加一除本數(shù)。不盡，又加一個(gè)方指數(shù)除之。依此屢加除之，視其能盡者，則本數(shù)非數(shù)根。不盡者，本數(shù)是數(shù)根。記本數(shù)為N，(N，10)=1。①術(shù)文未明確這一條件。例題滿足之。依次計(jì)算

據(jù)此，用李善蘭的結(jié)論判別N是否素?cái)?shù)。①當(dāng)d=2α?xí)r，只用即可判別N是否素?cái)?shù)。參見(jiàn)原書(shū)例題其中，

α =α1+α2+… +αm，1≤ki≤9 是正整數(shù)，αi=0，1，2，…，i=1，2，3，…，m。事實(shí)上，若

由此可知，該術(shù)給出滿足條件

的d的一種算法。其中表為純循環(huán)小數(shù)的充分與必要條件的另一表述是，其循環(huán)節(jié)長(zhǎng)度d滿足式(9)。

以上兩術(shù)是李善蘭“小數(shù)回環(huán)法”的進(jìn)一步完善。李氏以具體的例題說(shuō)明循環(huán)節(jié)長(zhǎng)度d可用除法求得。而后，以d判別N是否素?cái)?shù)。其術(shù)缺少一般性的表述及必要的理由。②李氏原術(shù)謂“其回環(huán)數(shù)有正負(fù)相間者，有有正無(wú)負(fù)者”，意義不明。華蘅芳《算草叢存》之七“循環(huán)小數(shù)考”稱“惟言回環(huán)數(shù)有正負(fù)相間者尚未考得?！逼澣源嬉伞１容^之下，《數(shù)根叢草》第19術(shù)與第14術(shù)方法更為完整。

第18術(shù):

置本數(shù)減一折半為方準(zhǔn)。視其內(nèi)有若干乘數(shù)，先取最大之一個(gè)乘數(shù)為約法之次數(shù)。乃置本數(shù)加一，以二約之，得數(shù)，又以二約之。不受約，又加一個(gè)本數(shù)約之。如是屢約，至適滿所定之次數(shù)而止。查其余數(shù)是否為一。是，則即以其次數(shù)為遞加數(shù)，以除本數(shù)。不盡者，是數(shù)根。否，則再以次大數(shù)減一，乘最大數(shù)為約法之次數(shù)。如前法約之。至所約之次數(shù)已滿方準(zhǔn)，仍不余一，則知其數(shù)非數(shù)根。若未滿次數(shù)以前能得余數(shù)為一，則其數(shù)亦非數(shù)根。

記本數(shù)為N，

中的d。若等于d，即d整除方準(zhǔn)，此時(shí)稱d“適滿所定(約法)之次數(shù)，余數(shù)為一”。由此可知，N可能是素?cái)?shù)，因d整除N-1。若“所約之次數(shù)已滿方準(zhǔn)，仍不余一”，即的任一個(gè)素因數(shù)或其相乘積均不等于d，依術(shù)可得除的素因數(shù)或其相乘積之外的滿足上述條件的d，即d不整除方準(zhǔn)，此時(shí)稱d“未滿(所定約法之)次數(shù)，余數(shù)為一”。由此可知，N不是素?cái)?shù)，因d不整除N-1。

為求得滿足條件的d且使的素因數(shù)或其相乘積不致遺漏，計(jì)算以約法之次數(shù)為序分段進(jìn)行，直至約得結(jié)果等于1或N-1為止，①術(shù)文“查其余數(shù)是否為一”包括等于1或N-1兩種情形。參見(jiàn)該書(shū)第3術(shù)及其例題。即得所求的d。

據(jù)此，用李善蘭的結(jié)論判別N是否素?cái)?shù)。②當(dāng)時(shí) d=2α，只用即可判別N是否素?cái)?shù)。參見(jiàn)后例其中，

該術(shù)求d的方法與第14術(shù)相同。以下舉例說(shuō)明其應(yīng)用。

判別N=37是否素?cái)?shù)。①本例不在《考數(shù)根法》與《數(shù)根叢草》之中。

第1段，以p1=3為約法之次數(shù)，依次計(jì)算

1+2=3=p1，余數(shù)不得 1。

第2段，以p1(p2-1)=6為約法之次數(shù)，依次計(jì)算

1+2+3=6=p1(p2-1)，余數(shù)不得1。

第3段，以p1p2(p3-1)=9為約法之次數(shù)，依次計(jì)算

1+3+5×1=9=p1p2(p3-1)，余數(shù)得N-1。

整除方準(zhǔn)，N=37可能是素?cái)?shù)。且，得數(shù)5已小于除數(shù)7。N=37是素?cái)?shù)。

判別N=341是否素?cái)?shù)。

第1段，以p1=17為約法之次數(shù)，依次計(jì)算

1+9=10=5 ×2=p2p3，余數(shù)得1。

d=p2p3=5×2，整除方準(zhǔn)，N=341可能是素?cái)?shù)。但不是素?cái)?shù)。

判別N=91是否素?cái)?shù)。

第1段，以p1=5為約法之次數(shù)，依次計(jì)算

2+1+2=5=p1，余數(shù)不得 1。

第2段，以p1(p2-1)=10為約法之次數(shù)，依次計(jì)算

7不滿約法之次數(shù)p1(p2-1)=10，余數(shù)得1。

d=p1+7=5+7=12=3×2×2，不整除方準(zhǔn)，N=91不是素?cái)?shù)。

該術(shù)是李善蘭“準(zhǔn)根分級(jí)法”的進(jìn)一步完善。李善蘭用“超乘補(bǔ)乘”求d，此處改用“累加累除”求d。當(dāng)N是多位數(shù)時(shí)，用超乘補(bǔ)乘雖較簡(jiǎn)便，但下列兩點(diǎn)亦屬明顯的不足。其一，求得

時(shí)，雖可判別N不是素?cái)?shù)，但因未能求得d而無(wú)法給出N的因數(shù)分解。為了分解N，李善蘭借助“天元求一法”另行求d。其二，雖可避免遺漏整除方準(zhǔn)的d，但可能遺漏不整除方準(zhǔn)的d。因而“準(zhǔn)根分級(jí)法”不是一個(gè)完整的方法。李善蘭就其法給出五5個(gè)例題。第5例是判別N=16637是否素?cái)?shù)。李氏給出

用超乘補(bǔ)乘求得

從而

顯然，4159×2=p1p2，已滿所定之次數(shù)，而余數(shù)不得1。據(jù)此，僅能判別N=16637不是素?cái)?shù)，而不能給出N的因數(shù)分解。“欲知本數(shù)之根，當(dāng)以大衍術(shù)入之?！崩钍狭碛锰煸笠环ń?/p>

得x=4636，即

再以4636為乘法，求得

由式(11)得

由式(12)得

由式(13)、(14)得

由式(10)、(15)得

即

由此可得

最后，取d分解

方氏第18術(shù)的關(guān)鍵是以“累加累除”求得d。方準(zhǔn)之設(shè)以及分段計(jì)算只為避免遺漏整除方準(zhǔn)的d。不設(shè)方準(zhǔn)亦不用分段，連續(xù)運(yùn)用“累加累除”即可求得d。仍以N=16637為例:①本題共迭代455次，計(jì)算由研究生劉軼明完成。

取d=910=13×7×5×2，分解N的結(jié)果同前。李善蘭用“超乘補(bǔ)乘”計(jì)算，因而遺漏了不整除方準(zhǔn)的d=910。其所得d=8190=910×9，顯非最小。比較之下，方氏第十八術(shù)雖計(jì)算次數(shù)較多，但確是一個(gè)完整的方法。參考文獻(xiàn)［5］遺漏了約得結(jié)果等于N-1的情形。若遺漏這種情形，則需要繼續(xù)“累加累除”方可求得1，從而使得計(jì)算次數(shù)成倍的增加。參見(jiàn)上述N=37的情形。

3 《數(shù)根叢草》兩項(xiàng)工作的簡(jiǎn)短分析

如前所述，《數(shù)根叢草》的內(nèi)容選擇與文字表達(dá)均存在不足。然而，在因數(shù)分解判別素?cái)?shù)法的應(yīng)用、李善蘭“小數(shù)回環(huán)法”與“準(zhǔn)根分級(jí)法”的完善等兩方面給出較為深刻的工作。其中可以第7術(shù)、第17術(shù)、第19術(shù)及第18術(shù)為代表。

因數(shù)分解判別素?cái)?shù)法是一種常用的方法。設(shè)N=ab，a＞b。當(dāng)a-b較小時(shí)，用第7術(shù)較為簡(jiǎn)便。當(dāng)a-b較大時(shí)，用第17術(shù)較為簡(jiǎn)便。茲以第7術(shù)為例說(shuō)明之。

李善蘭“準(zhǔn)根分級(jí)法”第4例N=13447，給出

取d=6720=168×40，判別知N=13447=119×113，不是素?cái)?shù)。由方氏第18術(shù)可得

取d=168，判別結(jié)果同前?！袄奂永鄢彼胐值為“超乘補(bǔ)乘”所得d值的，而計(jì)算次數(shù)則為74次。若改用方氏第7術(shù)則極為簡(jiǎn)單。

判別N=13447是否素?cái)?shù)。

由x2-N=y2，即

可知，N=13447不是素?cái)?shù)。

又如，上述李善蘭“準(zhǔn)根分級(jí)法”第5例N=16637，給出

取d=8190=910×9，判別知N=16637=131×127，不是素?cái)?shù)。由方氏第18術(shù)可得

取d=910，判別結(jié)果同前?！袄奂永鄢彼胐值為“超乘補(bǔ)乘”所得d值的，而計(jì)算次

數(shù)則為455次。若改用方氏第7術(shù)則極為簡(jiǎn)單。

判別N=16637是否素?cái)?shù)。

由x2-N=y2，即

可知，N=16637不是素?cái)?shù)。

以上兩例均為兩個(gè)因數(shù)之差a-b較小的情形。若N的兩個(gè)因數(shù)差較大，或N為素?cái)?shù)，則因數(shù)分解法的計(jì)算次數(shù)隨之增加。

以李善蘭的結(jié)論判別N是否素?cái)?shù)，須先求得d。求d的方法不同，所得d值大小亦即計(jì)算次數(shù)可能有明顯的差別。

例如，李善蘭“屢乘求一法”第1例N=31，給出

取d=5，判別知N=31是素?cái)?shù)。若改用“小數(shù)回環(huán)法”可得

或即

取d=15=5×3，判別結(jié)果同前。計(jì)算次數(shù)相差明顯。

再如，李善蘭“小數(shù)回環(huán)法”第1例N=271，給出

或即

取d=5，判別知N=271是素?cái)?shù)。若改用“天元求一法”可得

取d=135=5×27，判別結(jié)果同前。計(jì)算次數(shù)相差明顯。

又如，李善蘭“天元求一法”第2例N=63973，給出

取d=18，判別知N=63973=9139×7，不是素?cái)?shù)。若改用方氏第18術(shù)可得

取d=36=18×2，判別結(jié)果同前。計(jì)算次數(shù)相差明顯。

此外，上述李善蘭“準(zhǔn)根分級(jí)法”第5例N=16637，用“累加累除”與“超乘補(bǔ)乘”分別求得

亦屬此類情形。

以上4例可以說(shuō)明，不同的求d方法各有所用，不可偏廢。然而，對(duì)于給定的N，選擇何種方法求得d，事先難以預(yù)知。試算是不可缺少的工作?！犊紨?shù)根法》求d四法之下所設(shè)各例當(dāng)是試算之后的安排。因而，以李善蘭的結(jié)論判別N是否素?cái)?shù)，建立完整、簡(jiǎn)便的求d方法至為關(guān)鍵?！靶?shù)回環(huán)法”與“準(zhǔn)根分級(jí)法”的完善，其意義即在于此。

《考數(shù)根法》與《數(shù)根叢草》涉及的初等數(shù)論早期內(nèi)容主要有下列各點(diǎn):費(fèi)爾馬小定理，費(fèi)爾馬小定理的逆命題，純循環(huán)小數(shù)的循環(huán)節(jié)長(zhǎng)度與素?cái)?shù)的關(guān)系，費(fèi)爾馬因數(shù)分解法，合數(shù)的最小素因子，威爾遜定理，平方剩余的概念等。以上內(nèi)容在中國(guó)傳統(tǒng)數(shù)學(xué)中并無(wú)研究基礎(chǔ)。費(fèi)爾馬小定理的逆命題曾被認(rèn)為成立。1819年，薩呂斯(F.Sarrus)舉出反例，即2340≡1(mod 341)，但341=31×11，341不是素?cái)?shù)。李善蘭亦曾認(rèn)為費(fèi)爾馬小定理的逆命題成立。［8］《考數(shù)根法》改正了這一錯(cuò)誤，反例341亦出現(xiàn)在其中。華蘅芳、方士亦以該逆命題為真。此一現(xiàn)象中外頗為相似?！稊?shù)根叢草》自序稱，

該書(shū)光緒二十三年余經(jīng)華序稱，“去冬石印其《合數(shù)術(shù)》于滬”。以是知方士著有《合數(shù)術(shù)》一書(shū)。①華蘅芳、傅蘭雅譯《合數(shù)術(shù)》11卷(1887)，未刊，今傳稿本，是書(shū)有林紹清節(jié)本《合數(shù)述》二卷，光緒十四年序刊，其內(nèi)容源于Oliver Byrne，Dual Arithmetic:A New Art，London，1863。其內(nèi)容與初等數(shù)論無(wú)關(guān)。對(duì)于探討《考數(shù)根法》與《數(shù)根叢草》內(nèi)容與方法之來(lái)源，是書(shū)當(dāng)有重要意義。無(wú)奈迄今未見(jiàn)傳本，不得其詳。這一問(wèn)題的研究有待新的史料發(fā)現(xiàn)。

參考文獻(xiàn)

1 李善蘭.考數(shù)根法［J］.中西聞見(jiàn)錄.第2～4號(hào)，1872.

3 錢(qián)寶琮.中國(guó)數(shù)學(xué)史［M］.北京:科學(xué)出版社，1981.328～329.

4 嚴(yán)敦杰.中算家的素?cái)?shù)論［J］.數(shù)學(xué)通報(bào)，1954(4):6～10;1954(5):12～15.

5 張祖貴.《數(shù)根叢草》研究［J］.自然科學(xué)史研究，1992，11(2).

6 Ore O.Number Theory and Its History［M］.New York:Dover Pub.Inc，1976.57 ～58.

7 閔嗣鶴，嚴(yán)士健.初等數(shù)論［M］.北京:高等教育出版社，1957.78.

8 韓琦.李善蘭“中國(guó)定理”之由來(lái)及其反響［J］.自然科學(xué)史研究，1999，18(1).