（科学技术史专业论文）晚清数学家关于素数研究的成就与不足.pdf

摘要 中国古代的数论比较发达，但是一直没有出现素数概念。西方素数概念是在 明清时期由传教士传入中国的，始见于数理精蕴下编卷三十八，并译作“数 根 ，本文将以晚清素数的判定方法、性质和应用为主线，进行如下工作： 1 、详细介绍晚清素数传入中国的背景，通过对社会背景和学术背景的分析， 帮助后文系统地分析素数概念传入中国后对传统数学的影响； 2 、详细介绍李善兰素数判定方法、方士镰素数判定方法，华衡芳素数判定 方法，以及他们的判定方法之间的联系； 3 、系统考察晚清有关素数性质的著作，如数根演古、求乘数法； 4 、在吸收素数概念后，用于解决中国传统数学问题的研究； 5 、在相关著作的基础上，对晚清数学家关于素数的研究分析其成就和不足。 关键词：李善兰、方圭筷、华衡芳、数根、素数判定方法 a b s t r a c t a n c i e n ta ：l i n e s en u m b e ft l l e 0 巧w a l sd e v e l o p e d ，b u tn op r i m e p 痂n e 删m b c r w 弱i n 钉o d u c e di n t oc l l i i l ab ym i s s i o n a r i e sb e t 、) l ，e e i lm i n gd y l l a s t y 锄dq i n gd ) ，i l 鹊劬 w r h i c hf i r s ta p p e a r e di i l 鼬“缈以眇“刀( 数理精蕴) p a ni i v o l 3 8a n dw a st r a n s l a t e d i n t os 而m g p ，z t h i st h e s i sm a i l l l yd i s c u s s e st l l ed i s c r i m i n a t i o n s 、p r o p e r t i e sa i l du s eo f 砸m en 啪b e r si i ll a t eq i n gd ”a s 劬m em 咖j o b so f t h et l l e s i sa r e 嬲f o l l o w s f i r s t l 弘t 1 1 eb a c k g r o 珊do fi n 仃o d u c t i o no f 砸m es m d i 锱i l ld e t a i l a c c o r d i n gt 0 l ca i l a l y s i so ft l l es o c i a la n da c a d e i 】= l i cb a c k g r o u i l d ，i ti sr e a d y 蠡) rd i s c u s s i n gt h c i i l n u e i l c eo fc h i n e s e 仃a d i t i o n a lm a n l sa r c ra b s o r b i n g 研m en 瑚n b e r ss y s t e m a t i c a l l y s e c o n d l 弘l is h a i l l 趾、f a i l gs l l i r o n ga n dh u ah e i l 酎h g sd i s d m i n a t i o no f 硼m e n 啪b e ri nd e t a i l ，a n dm ec o n n e c t i o no ft l l e i rd i s c r i m i n a 矗o n s n i r d l y ，m i sm e s i s 删i e s 廿l ew o d 【o fp r o p 硎c so f 研m en 啪b e r si i ll a t eq i n g d y n a s t yi nd e t a i l ，s u c ha s 鼢烀垆馏”( 数根演古) 、9 ”幽e ，秽 斫i ( 求乘数 法) f o u n l l l y ，t h i st h e s i ss t u d i e sm eu s eo fp m et os o l v ct h ep r o b l e mo fc h i n e s e 仃a d i t i o n a lm a t h sa r e ra ：b s o r b i n gp r i m en u m b e r s f i n a l l y 0 nar e l e v 雒tw o 出b 嬲i s ，m e 砌埘w i l le v a l u a t em ea c c o m p l i s e i l t s a l l dd e f i c i e n c i e so ft l l es 锄i e so fp r i m en u l i l b e r so fm a n l e m a t i c i a n si nl a t eq i n g d y i l a s t y k e y w o r d s ：l is h a l l l a i l 、f a n gs m r o n g 、h u ah e l l g f ；m g 、舶z 蜓y 甩( 数根) 、 d i s c r i m i n a t i o no fp r i m en m 】m b e r s i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得苤盗竖整盘堂或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名：立丕驻日 期：麴幽刍卫_ l 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：一堑刍 导师签名： 天津师范大学硕士学位论文 第一童绪论 1 1 素数概念传入中国的相关背景 欧洲文艺复兴运动( 1 5 、1 6 世纪) ，完成了中世纪的文化向近代文化的过渡， 这场在文艺、哲学和科学领域内的革命运动促进了欧洲意识形态领域的变革和近 代自然科学的诞生。社会经济的迅速发展推动了自然科学的大踏步前进，在数学 方面1 8 世纪和1 9 世纪前半叶产生了一大批著名数学家，例如欧拉( 1 7 0 7 l 1 7 8 3 ， 瑞士人) ，拉格朗日( 1 7 3 1 8 1 3 ，法籍意大利人) ，高斯( 1 7 7 卜1 8 5 5 ，德国人) ， 柯西( 1 7 8 9 _ 1 8 5 7 ，法国人) ，罗巴切夫斯基( 1 7 9 3 1 8 5 6 ，俄国人) 等；在数学领 域内迅速成长起一簇簇新的分支，如分析、无穷级数、微分方程、微分儿何、变 分法、矩阵论、方程论、数论、非欧几何、射影几何等等。 在这样的背景之下，中国社会当时的政治、经济、文化却处在停滞甚至倒退 的状态。1 7 2 3 年，雍正皇帝一反康熙阜帝尊重西学的做法，下令禁止传教士在 中国的活动，此后一百多年，国内思想界、科学界、教育界处于与世隔绝的状态， 以乾嘉学派为代表，把注意力转向过去，整理国学，光复故物。朝廷官员妄自尊 大，以天朝上国自居，对西方的进步闭目塞听；有些守旧的学者认为国学广博， 西学纵有新技，不过古已有之，对国外的变化不愿了解也不能理解。但是这样的 状况不能持久，1 8 4 0 年，英国舰队的大炮轰开了闭关自守的中国大门，揭开了 帝国主义列强侵略中国的序幕，促使封建社会解体，把中国变成了半封建半殖民 地社会。中国社会的政治、经济和文化结构，面临着一场重大的变革，它关系到 国家民族的存亡，所以当时的有识之士，开始了长期的探索。继早期改良主义思 朝( 其代表人物是龚自珍、林则徐、魏源) 之后，又有一批科学家参加了洋务运动 ( 1 9 世纪6 0 年代到9 0 年代) ，这批知识分子的代表人物就是李善兰、徐寿、华 蘅芳川。 当时，在科学领域内，西方的成就遥遥领先。数学研究在乾嘉学派影响下虽 有回升，也有了一些变量数学的内容，但并未形成体系，总的来说还处于常量数 学的范畴。在这样的情况下，李善兰、华蘅芳等人把西方的数学介绍到中国来， 他们自己也从事了独立的研究。他们的部分工作主要表现在引进并建立了解析几 何、微积分、代数学、概率论等学科，使得近代数学得以在中国生根发芽口】。 早在公元前三世纪，希腊数学家欧几里得所著原本中卷到卷就有关 于素数、合数的定义和定理叩1 ： 卷中 定义1 l ，只能被单位量尽( 除尽) 的数称为素数。 定义1 2 ，互为素数的数是这样的数，只有单位是它们的共同量数。 定义1 3 ，能被单位以外的数量尽的数称为合数。 卷中 命题1 和命题2 讲求两个数的最大公度( 除数) 的方法，即辗转相减法。 命题3 讲求三个数的最大公度。 命题2 4 讲如果口和6 都与c 互素，那么动与c 互素。 命题3 0 ，如有素数能除尽两数的乘积，那么这个素数能除尽原来两数中的 一数。 命题3 1 ，合数可被某个素数除尽。 命题3 9 讲求几个数最小公倍数的方法。 天津师范火学硕士学位论文 卷中 命题1 4 ，如果一个数是能被几个素数除尽的最小的数，那么除了这几个素 数以外，再也没有其他的素数能够除尽那个数。1 命题2 0 ，有素数大于任何己知的素数。2 中国古代数学中没有素数和把一个正整数分解成素因子的概念。我国古代数 学家有“更相减损的方法求两数的“等数 ( 即最大公约数) ，相当于辗转相除 的欧几里得算法，亦有在分数计算时求分母最小公倍数的方法，但都没有用到素 数的概念。 西方素数概念是在明清时期由传教士传入中国的，始见于数理精蕴下编 卷三十八，并译作“数根 ，其中对数阐微给出一个素数表，李善兰与伟烈 亚力翻译几何原本后九卷时，也涉及到素数概念，他们沿用了“数根”译名。 素数判别方法的研究，始于清末数学家李善兰( 公元1 8 1 1 一1 8 8 2 年) 的考 数根法( 1 8 7 2 年) ，这是我国近代素数论方面最早的论著，提出素数判别的充 分必要条件，随后，华蘅芳( 公元1 8 3 3 一1 9 0 2 年) 又著数根术解。讨论了李 善兰的方法，并论述了算术基本定理等内容。在李善兰素数论的基础上，方士镰 在1 8 9 6 年完成的数根丛草中提出了2 0 种判别素数的方法，不少都具有独创 性，将素数判别理论推向了一个新的高度。此期间还出现了关于中算家接受素数 概念后，对素数应用的一些著作，如1 8 7 4 年，清代学者黄宗宪在求一术通解 卷上的析根法一素因数分解法后，介绍了他的求定母法，黄宗宪把从西方数学 中引入的素数概念同中国人长期占领先地位的一次同余式组问题结合起来，提出 了素因数分解求定母法。还有华蘅芳的开方别术一卷( 1 8 7 2 年) ，副题为数 根开方术，该书讨论整系数方程有理根的解法。值得注意之处是将素因数分解引 入中国传统数学的增乘开方法，从而使有理根的求法大为简化。 1 2 研究的必要性 近年来数学史界一个比较重要的研究方向就是晚清西学的传入及对中国传 统数学的影响这个问题。素数的概念完全是由西方传入的，那么，中算家接受此 概念时的效果如何? 晚清数学家关于素数研究的成就都有哪些? 不足又有哪 些? 这些是有待研究的。 李善兰素数判别法的优点是实用性强，计算量小，他的工作相当于证明了 f e 咖a t 小定理并指出其逆定理不成立，此方面为吸收素数概念后的再发展，而华 蘅芳再研究f e m a t 小定理时并没有注意到f e m a t 小定理的逆定理不成立，为什 么晚清有的数学家在同样的学术背景下，仍在接受素数理论上有误解? 这个问题 是值得我们深思的。 研究晚清素数内容传入是晚清数学史的一个重要方面，对我们更好的看清中 国数学发展的脉络，认识中算家数学思想，以及在中西文化交融的这段时问里， 中西文化的发展趋势有很大的帮助，故有进一步研究的必要，而以往在这方面的 研究性著作相对较少，内容也欠完备，故笔者将选择晚清有关素数理论的典型著 作，从素数的判定、素数的性质、素数的应用这几方面分析中算家接受素数概念 的情况，吸收的好的方面和不足的方面。 1 这就是说，如果4 是素数a ，见，的乘积，那么将彳分解成素数乘积的方法是唯一的。这么命题称为算 术的摹本定理。 2 这就是说，素数的个数是无限的。 2 天津师范大学硕士学位论文 国内外关于晚清素数研究的文献有： l ，严敦杰：中算家的素数论，载数学通报1 9 5 4 年4 月号第6 1 0 页， 5 月号第1 2 1 5 页。 2 ，张祖贵：数根丛草研究，载自然科学史研究第1 1 卷第2 期( 1 9 9 2 年) ：1 2 7 1 3 8 3 ，吴文俊主编：中国数学史大系第八卷北京：北京师范大学出版社1 9 9 9 4 ，p 里本伯姆著，孙淑玲、冯克勤译：博大精深的素数北京：科学出版 社2 0 0 7 严敦杰( 公元1 9 1 7 1 9 8 8 年) 教授的中算家的素数论二文对考数根 法、数根术解进行了比较详尽的研究。张祖贵数根丛草研究一文对清末 数学家方士铼的数根丛草进行了研究。吴文俊主编的中国数学史大系第八 卷分专题对中国中算家及其著作进行了阐述，但是以上研究文献对于方士铼的 素数判定方法思想没有深入的剖析，也没有指出其法和李善兰方法的联系，其中 数根丛草第十七术解释有误，第二十术解释有遗漏。因此本文将在前人研究 的基础上，进一步阐明素数判定方法的数学思想，以及各方法的联系和区别，将 前人有误和遗漏的地方改正。 前人的研究为我们的工作奠定了坚实的基础。在前人研究的基础上，首先对 晚清有关素数著作进行系统的分析，从而研究自素数概念传入中国以后，中算家 吸收和理解素数概念的效果及其原因，分析此后是否继续有所发展和创新，本文 还将进一步讨论传入的素数概念和中国传统数学方法的联系及对中国传统数学 方法起到的作用和影响。 本文主要采用文献法和比较法，从分析和解读考数根法、数根术解、 数根演古、数根丛草、求一术通解、求乘数法等原始文献资料入手， 以具体史料内容作为比较研究的基础。在文献资料研究方法的基础上，结合具体 问题的研究，借用其他学科的视角和研究方法，如借用数学的推理分析方法分析 当时中算家的主要思想。本文还将充分利用二次文献进行逻辑分析、归纳总结， 尽量避免只是对文献资料进行简单的罗列和整理。 1 3 本文主要研究工作和相关结论 首先，本文对李善兰考数根法进行了系统的研究，考数根法中给出 的屡乘求一法、天元求一法、小数迪坏法、准根分级法，这四种判定素数的方法， 实际上这四种方法的数学思想是相同的，“四种 实际上是给出四种计算指数d 的 方法。并且本文重点研究考数根法前两法，其在中国数学史上具有重要的价 值，而小数迪环法只是给出相关步骤和结论，并没有将此法的素数判定原理讲清 楚，也没有把循环小数的循环节长度和定次d 的关系讲明。准根分级法从计算量 上考察，这个算法比较笨拙且实用价值差，故此法实用价值不如前三法。 其次，本文对方士锑数根丛草中2 0 个素数判定方法的数学思想进行了 深入的剖析和归纳总结评价，具体指出各个方法在数学思想上和李善兰判定方法 之间的联系和区别，这方面的讨论是以往研究者没有涉及到的。已有的某些解释 还存在数学意义不清或错误，本文也作了进一步的讨论。现有的研究文献对于方 士铼的第十七术解释有误，第二十术解释有遗漏，故本文都将予以改正；第三、 十四、十五术是对李善兰求d 方法的推广，实际上是在李氏求j 方法的基础上又 给出新的方法；第十九术和李氏小数逼环法思想是一致的，但前者算法相对比较 天津师范大学硕士学位论文 好，把循环小数的循环节长度与的关系解释清楚了，推广了李善兰小数迪环法； 第六、七、八、九术是利用等差数列巧妙的来凑完全平方公式的方法进行素数判 定的；第十六术是利用解不定方程来作素数判定的；此外第二术是利用平方剩余 及既约剩余系理论作素数判定；还有利用素数定义进行判定的，如第一、第四、 第五术。其中方士镰数根丛草中第三、六、七、八、九、十四、十五、十七、 十九、二十这几种素数判定方法的结论都是以前研究者没有获得的，本文独立获 得的；而第一、二、四、五、十、十一、十二、十三、十六、十八这几种素数判 定方法的结论是在以前研究者的结论基础上进一步研究得出的。 再次，本文对方士锑数根丛草中错误的第十、十一术和华蘅芳数根术 解中错误的素数判定方法从数学思想上进行原因分析。 最后，本文系统考察和整理了华蘅芳著作求乘数法、数根演古，从而 总结晚清数学家关于素数分解性质和制作素数表的工作。 4 天津师范大学硕七学位论文 第二章晚清关于素数的判定 2 1 李善兰素数判定法 2 1 1 李善兰1 考数根法思想来源 中国古代的数论比较发达，但是一直没有出现素数概念。素数，早期译为数 根，是在明清时期由传教士传入中国的，数根词最早出现在清初编篡的数理 精蕴( 1 7 2 3 年) 下编卷三十八，其中对数阐微给出一个素数表。李善兰、 伟烈亚力翻译几何原本后九卷( 1 8 5 7 年) 时沿用数根词，见该书卷七。 但是这些著作中都没有论及素数判定的方法，“任举一数欲辨其是数根否，古无 法焉。 很长一段时间人们都认为3 4 1 这个数是素数，而在李善兰考数根法中却 判定了3 4 l 不是素数，那么李善兰为何想到去研究判定素数的方法，当时他又是 如何得出“中国定理”2 的? 其中的西算传入背景应该比我们想象的要多。 首先，本文认为李善兰研究判定素数方法的原因和西学传入有很大关系。从 中国的传统数学脉络来看，是一直没有素数概念的，也是接触不到f e 册a t 小定 理的，因此李善兰作素数判定方法的研究，和西学传入有很大关系。因为从1 8 5 2 年起，李善兰到上海，有八年时问与英国人伟烈亚力( a l e ) 【a i l d e rw y l i e ，1 8 1 5 一1 8 8 7 年) 、艾约瑟( j o s 印he d k i n s ，1 8 2 3 一1 9 0 5 ) 等合作进行翻译，外国人口述，他作 笔录，正因为他和传教士合译西方著作，他才有更多的机会接触西方数学。同时 1 8 6 8 年李善兰任京师同文馆算学总教习也会接触很多外国人，同文馆原是培养 英、法、俄语翻译的高等学校，后增设天文和算学等科。n 1 其次，我们也可考察与李善兰同时代的数学家著作，如方士铼数根丛草 序中，曾提到李善兰考数根四法全从合数得来，但因合数术及方士铼另一著 作南郡书院算学课艺迄今尚未查到，所以具体李善兰考数根法内容的思 想来源尚未查清。 “考数根古今无通术，惟近世西学几何原本颇论其理，然未明言其所以 考求之术。海宁李壬叔( 善兰) 先生曾创四法，惜乎近人鲜有证其源者，是以未通 行于世。士镰于丙申孟夏校释合数，门人邓启昆以所录李先生考数根四法求 解。士铼细加推索，知李法全从合数得来，始叹先生生平于西学诸书搜览可谓博 矣。释合教既毕，乃于李法外别创廿法，不揣固陋，付诸褚墨，非敢与先生角胜， 聊为世之读先生四法而莫解者，或者睹士镣渚术，多所触类而引伸也“1 最后，在韩琦所写李善兰“中国定理”之由来及其反响一文中提到李善 兰素数判定思想源于贾宪三角形，因他对二项式定理非常熟知，故会很容易地得 到下式： 2 = ( 1 + 1 ) 。 ：l + z + 兰螋+ + 兰! 三二! ! ：! 查二兰! ! + x + 1 21s ! 若z 为素数，除首项、末项外，每一项具有，搬的形式，这里聊是一整数，故展 。李善兰，字壬叔，号秋纫，原名心兰，浙江省海宁县人。 2 “中国定理”：若2 ，一2 兰0 ( m o d p ) ，则p 为素数，也就是f e n i l a t 定理的逆定理。 天津师范大学硕上学位论文 开式的每一项均可被x 整除。因此，2 。= 1 + ，珊+ 1 ，2 = 肌，李善兰判断石是 工 否为素数的方法应由此式反推而成1 。这一工作在博大精深的素数一书第 9 0 页有所反映。 1 8 7 2 年，李善兰发表考数根法 ，发表于艾约瑟主编的中西闻见录 第二、三、四号，讨论了素数的判定法，这是国人关于素数研究的最早的工作， 但我们注意到：在考数根法中，“中国定理已被删去，其中缘由如何? 李善兰曾把“中国定理交给德国人方根拔( j v o ng 啪p a c h ，卜1 8 7 5 ) ，方 根拔身在其中，熟悉讨论的详情，另有证据表明方根拔的朋友曾向李善兰指出“中 国定理”之谬哺1 。此外，伟烈亚力、傅兰雅等与李善兰有密切来往的欧洲人也有 可能告诉他事实的真相，因此李善兰对欧洲人有关此定理的讨论有所了解，这也 许是他在发表考数根法时没有刊登“中国定理 的重要原因。 2 1 2 李善兰考数根法中素数判定方法 欧拉( l - e n l 1 7 0 3 一1 7 8 3 ) 定理和费尔马( p f e n n a t 1 6 0 l 一1 6 6 5 ) 小定理是数 论中的两个重要定理，李善兰考数根法所论素数判别法即与上述两个定理有 关。 欧拉定理：设 1 是整数，( 口，加= l ，则口似) 兰l ( m o d ) 。 费尔马小定理：若是素数，( 口，忉= l ，则口- 1 暑l ( m o d ) 。 李善兰考数根法的主要结论可以表述如下。设，口是正整数，( ，口) = l ， 求得最小正整数d 使得 口。兰1 ( m o d ) ( 1 ) 其中，d 称为“定次”。是素数的充分必要条件是，d 整除一l ，且任一形如 印+ 1 的数不整除。其中，七，p 是正整数，p 整除d 。 此法满足欧拉定理和费尔马小定理，事实上，若有口d 暑l ( m o d 加，则必然有 di 纵) ，当为素数时，纵忉= 一1 ，故有di 一1 。李善兰在这里相当于证 明了该定理，同时指出，费尔马小定理的逆命题不真，即若( 口，加= 1 ， 口j 三l ( m o d 聊，且d l 一l ，则未必是素数。不仅如此，李善兰素数判定定理 的后半部分给出一个附加条件，即若d 的任何一个因子p ，有印+ l 不整除， 则是素数，该条件使得李善兰素数判定定理成为充要条件，是非常可贵的成 就。鉴于需判断的大多应是奇数，李氏规定如p 是奇数，可以l + 2 助进行试 算，此举亦减少了计算量口1 。 上述方法是考数根法的重点和基础，以下的例题选自原书。 判别= 3 1 是否素数。 取口= 2 ，求得2 5 童1 ( m o d 3 1 ) ，即d = 5 。因3 1 = 5 6 + 1 ，即5 整除( 3 l 1 ) ， 1 10 且_ 睾- = 2 + 三，得数2 已小于除数1 1 。“度之余一，除之不尽。 故3 1 是素 z x ) 十ll l 数。 判别= 3 4 1 是否素数。 取口= 2 ，求得2 加兰l ( m o d 3 4 1 ) ，即d = 1 0 = 2 5 。因3 4 1 - 1 0 3 4 + 1 ，即l o ， 1 整除( 3 4 1 一1 ) ，但睾= 3 1 。“度之得一，除之恰尽。 故3 4 1 不是素数。 6 天津师范大学硕士学位论文 判别= 1 4 2 0 9 是否素数。 取口= 3 ，求得3 2 1 暮1 ( n l o d l 4 2 0 9 ) ，即d = 2 1 = 3 7 。因1 4 2 0 9 = 2 1 6 7 6 + 1 3 ， 即2 1 不整除( 1 4 2 0 9 1 ) ，“度之不得一。，故1 4 2 0 9 不是素数。喜笺尝：1 0 9 3 。 判别= 1 0 3 是否素数。 取口= 2 ，求得2 5 1 暑1 ( m o d l 0 3 ) ，即d = 5 1 = 3 1 7 。因1 0 3 = 5 1 2 + 1 ，即5 1 整邮。3 - 1 ) 。且罴 1 4 + 号，忐- 7 + 吾，得数7 卧于除郯。墨， 云等籍2 2 芸，得数2 已小于除数3 5 。“度之得一，除之不尽。 故1 0 3 是素数。 上述的判别法须先求出指数j 。显然，给定，口，可由式( 1 ) 直接计算。 当d 较大时，计算量随之增大。为减少计算量，李善兰给出四种求指数d 的算法， 即屡乘求一法、天元求一法、小数迪环法、准根分级法。 计算中用到以下的术语： 本数：，即所要判别的正整数。 用数：口，多取口= 2 ，或口= 3 ，( 口，忉= l 。 正数：口”，刀= 0 ，1 ，2 ，。 负数：一口”，如，= 8 7 ，口= 2 ，则8 6 是2 0 的负数，8 5 是2 1 的负数，8 3 是2 2 的负数，等等。 屡乘求一法，原文是： “法以用数之诸方积，或大于本数，或大于本数之半者，与本数相减， 余为乘法。乘法自乘，或再乘，以本数度之。不尽，复以乘法乘之，以本数 度之。不尽，复以乘法乘之，以本数度之。如此逐求，至不尽数为诸正数， 或诸负数而止。乃计公用乘法若干次，以次数乘用数之方数，为泛次若不 尽数为一，或一之负数，则泛次即定次。若为诸方积，或诸方之负数，则以 其方数减泛次，为定次以定次度本数，若所余非一，则本数非数根；若余 一，则视定次为何二数相乘之积，其相乘数为偶者，即为递加数，为奇者， 倍之为递加数。乃置一，加一递加数，再加一递加数，如此递加，以递除本 数，恰尽即止。若至得数小于法，仍不恰尽，则本数是数根。“司 上述求定次d 的过程可作如下的解释。 设口“ ，则以口“一为乘法。逐步计算 ( 口“一聊s 暑足( 1 n o d m ( 口”一) 墨毫恐( m o d ) ( 口“一) 足兰足( m o d 加 ( 口”一) 吃兰b + ，( m d d 忉 其中，吃+ i = 口f 或吃+ i = 一，s = 2 ，3 ，掰= o ，1 ，2 ，f = 0 ，1 ，2 若吃+ 。= 口，则由同余的性质，得 ( 口”一忉”r r 也主曩足b b 吃+ 。( m o d 忉 即 7 天津师范大学硕七学位论文 ( 以4 一) 什”兰口( n l o d ) 化简为 口小j + 卅毫口( m o d 忉 亦即 口烈什脚叶量l ( m o d ) 其中，拧o + 柳) 称为泛次，而j = 刀0 + 加) 一f 即所求定次。显然， 即定次。 若也+ 。= 一口，贝i j ( 口”一) “基一订( m o d d 化简为 口瓜n 神暑_ 口( m o d ) 或即 ( 2 ) 当，= o 时，泛次 ( 3 ) 口2 “+ ”) 兰口2 ( m o d ) 亦即 口2 h ( 什“) 一2 未l ( m o d ) 由此可得定次d = 2 ，z 0 + 加) 一2 f 。同上，当f = o 时，泛次即定次。可见，原文所 说“若不尽数为一，或一之负数 分别是“若为诸方积，或诸方之负数”的特殊 情形，即式( 2 ) 或式( 3 ) 中f = o 的情形。 设芸 矿 ，或竺 口一 马 成。 再递求余数。 以用数准大根：口n 兰( m o d ) ， 以余数准次大根：，；见暑( m o d ) ， 以余数准第三根：n 兰( m o d 忉， 以余数准第，z 根：一，办兰，：l ( m o d 加， 型 于是得口j 口l 乃胪 善( m o d ) ，即口2 三( m o d ) 。 如有j 使得兰l ( m o d ) ，l s 刀，则令d = a p 2 只，则有口4 兰1 ( m o d ) ； 否则若1 ，则非素数；若，：= 一l ，则d = 一l 。余法如前。 李善兰准根分级法思路是先求本数的素因数，再寻找余数，和前三个方法 有所不同，但是从计算量上考察，这个算法比较笨拙且实用价值差，当本数较大 时，它的素因子个数是比较多的，若逐一找出再运算则计算量会很大，因此此法 实用价值不如前三法。 2 1 3 小结 李善兰的考数根法是中国第一部素数论专著，他在不了解西方的素数论 研究成果的情况下，独立地获得了f 锄a t 小定理的相关结果，尽管晚于欧洲， 但反映了李善兰乃至中国数学家的数学能力与水平，特别是他开清末素数论研究 之风，在国内外产生一定的影响。华蘅芳在李善兰的影响下著数根术解，其 中也讨论这一命题，但华氏对f e m a t 小定理的逆命题误以为真。 李善兰考数根法中的屡乘求一法、天元求一法、小数迥环法、准根分级 法数学思想是一致的，主要思路都是设，口是正整数，( ，口) = l ，求得最小正 整数j 使得口d 三l ( m o d ) ，是素数的充分必要条件是，d 整除一1 ，且任一 形如助+ 1 的数不整除。其中前两法在中国数学史上具有重要的价值，而小数 迪环法只是给出相关步骤和结论，并没有将此法的素数判定原理讲清楚，也没有 把循环小数的循环节长度和定次d 的关系讲明，后来方士锑数根丛草第十九 术将这一问题彻底解决了。准根分级法从计算量上考察，这个算法比较笨拙且实 用价值差，故此法实用价值不如i j 三法。 天津师范大学硕士学位论文 2 2 方士镁素数判定法 李善兰考数根法发表之后，方士谍数根丛草1 ( 18 9 7 年) 又给出新的 判别法。方士镰，字梅荪，湖北天门人，活动于清末年间，生卒年代不详，长于 舆地与数学。除此书外，据记载1 方士铼另有数学著作合数术( 18 9 8 年上海石 印本) 2 和南郡书院算学课艺，这三部著作在内容上有密切的关系。 数根丛草在李善兰素数论基础上，共给出考数根法二十术和二十二个例 题，将清末素数论研究推向了一个新高峰引。 此节为本文的重点之一，对方士铼数根丛草中2 0 个素数判定方法的数 学思想进行了深入的剖析和归纳总结评价，具体指出各个方法在数学思想上和李 善兰判定方法之间的联系和区别。 2 2 1 李善兰素数判定法的简化或推广 数根丛草中第三、第十四、第十五术是对李善兰求d 方法的推广，实际 上是在李氏求d 方法的基础上又给出新的方法；第十八术是对李氏“准根分级法” 算法的简化；而其第十九术进一步完善了李善兰小数迥环法，把循环小数的循环 节长度和定次j 的关系阐明了。 第三术日： “置本数已减一，得已t 一。任取一数甲约之。视其能否度尽。不尽， 加任倍已度之，得百f 品。又度之不尽，又加任倍已度之，得 甲二 ( 已t 一) 任倍已 任倍甲已9 又度之不尽，又加任倍已度之，得丌五= 可蟊甄王西蜀蓼再互丽 如是屡度至余一而止。视甲之方指数若干。即以方指数为递加数，偶者或半之为 递加数，及以递加数加一，除本数不尽，又加递加数除之。除尽者非数根，不尽 者是数根( 凡递加数已过本数之半，而仍除不尽，则知本数是数根) 。 n 1 1 对于本数，取口使得( 口，忉= 1 ，以进行四步为例，则有 兰竺删 兰三 兰：竺：旷- 口 【1 1 ) 当结果等于一1 时： 化简上式， 一l = 口啦+ 啦+ 吩+ q 一口确+ 啦+ 龟颤一口q + 啦毛一口q 毛一口q + 啦+ 吩+ 嘞 口口i + 电+ 码+ = 删+ 1 口q + 啦+ 码+ 。，羞1 ( m o d ) 李俨近代中算著述记见：李俨、钱宝琮科学史伞集第六卷沈阳：辽宁教育出版社，1 9 9 8 5 1 3 2 此处所说的合数术迄今未查到，是否传世小详。 1 2 天津师范大学硕士学位论文 口4 三1 ( m o d ) ，其中d = q + + 鸭+ 吒 2 ) 当结果等于1 时： 化简上式， 一1 = 口q + 勉+ 码+ q 一口q + 啦+ 吻织一口嘶+ 嘞舷一口q 舷 口口i + 吻+ 吩+ 口4 + 1 = 五： 口嘶+ 嘞+ 电+ 暑一1 ( 1 l 】l o d ) 口。兰一1 ( m o d 忉，其中d = + + + 吼 口2 4 三1 ( m o d ) 此术思想是为了求出满足口4 暑1 ( m o d 加的j ，其中保证所取的口和本数互 素，是素数的充分必要条件是，d 整除一1 ，且任一形如细+ 1 的数不整除。 其中，后，p 是正整数，p 整除d 。第三术以及后面的第十四术、第十五术是在求 d 算法上给出新的方法。 现举原书一例来说明此术的数学原理，试判别= 5 1 是否为数根。 = 5 1 ，取口= 2 ，则满足： 兰坚+ 5 1 _ + 5 l 一兰+ 5 1 l + 5 1 2 一+ 5 1 2 一+ 5 1 2， = 5 0 = 5 1 1 化简此式得， 5 l l = 2 8 ( 5 l 1 ) 一2 7 5 1 2 6 5 1 2 5 5 1 2 4 5 l 一2 3 5 l 一2 5 l 5 1 1 = 2 8 5 1 一( 2 7 + 2 6 + 2 5 + 2 4 + 2 3 + 2 ) 5 1 2 8 5 1 1 = ( 2 8 2 7 2 6 2 5 2 4 2 3 2 ) 5 l 一2 8 2 8 一l = ( 2 8 2 7 2 6 2 5 2 4 2 3 2 一1 ) 5 1 即2 8 董1 ( m o d 5 1 ) ，其中d = 1 + 2 + 1 + 1 + 1 + 1 + 1 = 8 。 则5 l = ( 8 + 1 + 8 ) 3 = 1 7 3 ，所以5 1 不是素数。 第十四术日： “置本数减一，以十约之，不尽，加若干个本数约之，为第一数；又将 第一数以十约之，不尽，内加若干个本数约之，为第二数；如是屡约至第几数始 为一，或等于本数减一，乃计所约若干次，如末数为一，则将次数倍之，为方指 数，如末数为本数减一，即以次数为方指数，于是以方指数为递加数，加一除本 数，不尽，又加一个方指数除之，依此屡加除之，视其能尽者，则本数非数根， 不尽者，本数是数根。“u 1 此法与第三术同类，但是口= l o ，对于本数，此术用1 0 去除，而非任意 数，仍以进行四步为例，则有： n 墨+ k n 1 q 羔二+ t ! ! 盘三二竺- t 1 0 q 1 1 1 3 天津师范人学硕士学位论文 1 ) 当结果等于一l 时： 化简上式， 一l = 1 0 q + 眈+ 吩+ 瓯一1 0 + 啦+ 吩缸一1 0 + 啦乞一1 0 q 毛一1 0 嘶+ 啦+ 码+ 口 1 0 q + 勉+ 约+ = 剧+ 1 1 0 嘞+ 吻+ 码+ 口兰l ( m o d 加 1 0 d 量l ( m o d ) ，其中d = q + + 吧+ 2 ) 当结果等于1 时： 化简上式， 一l = l o q + 吒+ 吻+ 瓯一l o q + 啦+ 啦缸一1 0 嘶+ 口2 欲一l o 确毛 1 0 q + 啦+ 白+ + l = 删 l0 q + 啦+ 妁+ 毫一1 ( m o d 加 l o d 毫一l ( m o d 忉，其中d = + + q + 1 0 2 0 羞1 ( m o d ) 注：( 口，加= l 是口d 蔓1 ( m o d 忉有解的充分条件，因此这里需要注意本数 ( 1 0 ，忉= 1 即要和2 或5 互素。李善兰素数判定方法选择用数多用2 或3 ，而 方氏选择l o 。 现举原书一例，试判别= 9 l 是否为数根。 婴j + 9 l 争= l ，化简此式得9 1 。= 1 0 3 9 1 1 o 1 0 3 + 1 = 9 1 ( 1 + l o ) 1 0 3 兰一1 ( n l o d 9 1 ) 1 0 缸2 兰l ( m o d 9 1 ) ，其中d = 2 3 = 6 即6 为方指数，则9 l = ( 6 + 1 ) x 1 3 = 7 1 3 ，所以9 1 不是素数。 第十五术日： “先将十以本数度之，不尽，又以十乘余数，以本数度之，不尽，又以 十乘余数，度之，至所余之数为一而止，乃计所乘若干次，即以次数为递加数， 加一除本数不尽，又加一个次数除之，除尽者非数根，不尽者是数根。“啪 对于本数， 1 0 口荸( m o d 忉， 1 0 兰吃( i n o d 忉， 1 0 吒三( m o d ) ， 1 0 乞暑名+ 。( m o d 忉，若+ ，= 1 ，则停止运算。 则1 0 口l o ”吒名兰，；吒乞，：，l + l ( m o d ) ， 因为( ，m = 1 ，( 眨，忉= 1 ，( ，忉= 1 ，( 名，加= l 所以1 0 甜m 三，= ，l + l ( m o d 忉，当名+ l = l 时，则d = 口+ 朋。 此法和李善兰屡乘求一法思想一致，只是度法不一样，在实际运用此法计算 判定时，要注意条件( 1 0 ，) = l ，即要检验一下是否和2 或5 互素。 现举原书一例，试判别= 2 4 7 是否为数根。 1 4 天津师范大学硕士学位论文 = 2 4 7 ，1 0 3 兰1 2 ( m o d 2 4 7 ) ， 1 0 6 羞1 4 4 ( m o d 2 4 7 ) ， 1 0 9 量2 4 6 ( m o d 2 4 7 ) ， 1 0 9 量一1 ( i n o d 2 4 7 ) ， 1 0 9 x 2 毫l ( m o d 2 4 7 ) ，其中d = 1 8 = 2 9 = 2 3 3 因为石筹备= 1 3 ，2 4 7 = 1 9 1 3 ，所以2 4 7 不是素数。 记本数为，以盟= 为方准，将其素数分解： 冬：卉乃，其中局 n b 办均为素数。 掣2 k ：；2 隆竺。 半乞= ：咋隆三，。 当f 丛芸，且1 ，则为合数； 些；：4 5 ：3 3 5 ，先取最大素因子5 ，作如下演算： 邑：掣：4 6 一：誓瑙，邑：半_ 5 7 ， _ ：半- 7 4 拍：学- 3 7 1 5 天津师范大学硕士学位论文 = 丝孚= 6 4 ，乞= 譬= 3 2 ，毛= 孚= t 6 ，= 萼= 8 ， f 5 = 兰= 4 ，f 6 = 三= 2 ，岛= 詈= 因为7 ， 么2 一+ ( 2 彳+ 1 ) + ( 2 彳+ 3 ) + ( 2 么+ 5 ) + + 【2 彳+ ( 2 以一1 ) 】= 口2 彳2 一+ 2 么，l + 【1 + 3 + 5 + + ( 2 刀一1 ) = 曰2 彳z 一+ 2 彳以+ ! ! 三! 二1 2 刀：男z 2 彳2 一+ 2 彳刀+ 门2 = b 2 ( 么2 + 2 彳以+ 刀2 ) 一= b 2 。( 么+ 咒) 2 一= 口2 = ( 彳+ 刀) 2 一b 2 r 其中，当么2 + 2 么以+ ，z 2 一( 芸) 2 时，原式还不能等于召2 时，则为素数， z 否则为合数。 例如，判别= 7 3 1 3 是否为素数。 彳2 = 8 6 2 = 7 3 9 6 ，彳2 一= 8 3 ， ( 爿2 一) + 2 彳+ l = 8 6 2 7 3 1 3 + 2 8 6 + 1 = 2 5 6 = 1 6 2 = 曰2 彳2 + 2 么+ 1 = ( 彳+ 1 ) 2 = 8 7 2 ，7 3 1 3 = 1 0 3 7 1 ，因此7 3 1 3 不是素数。 第八术日： “四因本数加四，开平方不尽，又加三个四，开之不尽，又加五个四开 之，于是屡加至开方适尽而止。乃以开得之根为和，所加之根为较。和较相加减， 即可得大小两乘数，则知本数非数根；如所加之平方根，已大于本数，则知本数 是数根”。n 妇 此术涉及一个等差数列4 l ，4 3 ，4 5 ，4 7 ， 对于本数， 4 + 4 + 4 3 + 4 5 + + 4 ( 2 ，l 一1 ) 】= 曰2 ， + l + 3 + 5 + + ( 2 ，l 一1 ) 】= 召2 ， 4 ( + ，1 2 ) = b 2 = 等卅2 = ( 罢删( 詈卅) ， 其中，当2 ，l 时，原式还不能等于艿2 时，则为素数，否则为合数。 例如，判别= 1 8 7 是否为素数。 1 9 天津师范大学硕士学位论文 4 1 8 7 + ( 4 + 4 3 + 4 5 ) = 2 8 2 ， 1 8 7 = 等一5 2 = ( 萼+ 5 ) ( 争5 ) _ 1 7 1 l ，所帅7 不是素数。 第九术日： “四因本数开平方，取其负余数为实置于上，倍方根加一，以加上位， 开平方不尽，又倍方根加三，以加上位开之，于是屡加，至开方适尽而止。乃以 开得之方根为和，所加之方根为较，和较相加减，可得大小两乘数，则知本数非 数根。若其所加之根数已近本数，则本数是数根”。n 妇 此术涉及一个等差数列2 么+ l ，2 么+ 3 ，2 彳+ 5 ，2 彳+ 7 ， 对于本数，若4 = 彳2 一，使 ，+ ( 2 彳+ 1 ) + ( 2 彳+ 3 ) + ( 2 彳+ 5 ) + + 2 么+ ( 2 力一1 ) 】) = 曰2 ，即 4 = 名2 + ( 2 彳+