欧几里德算法与相关问题的研究

《欧几里德算法与相关问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、●原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：丛生垒辛日期：>口plS．垆关于学位论文使用授权的声明本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本

2、学位论文。(保密论文在解密后应遵守此规定)论文作者躲幽彳导师躲丑3日期：一●●◆第三章欧几里德算法与素数的无穷性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．313．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯二⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3l3．2Dickson猜想的等价形式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．323．3刀上的线性多项式映射的一个性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．38参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．43致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．49个人简历⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．5l34●■山东大学博士学位论

3、文欧几里德算法及相关问题研究张韶华山东大学数学学院密码技术与信息安全教育部重点实验室摘要本论文主要研究了欧几里德算法及其相关的问题。在第一章，我们简单介绍了欧几里德算法及其应用。利用欧几里德算法，可以判定正整数序列al’⋯，am(11)个随机的正整数两两互素的概率是忐，其中“．)是RiemannZeta函数。这样，在正整数日l’．⋯am中，有一个正整数砚与其他数都互素的概率是(杰)肛1．若存在一个自然数，．(1≤，．≤m)使得a，与序列中的其他数都互素，则称l

4、们进一步分析了W序列的性质。我们证明对于整数，l>l，m≥l，如果有一个素数在序列m+1⋯．，m+n中，那么这个序列是一个w序列。这样，判定一个连续正整数序列是否是w序列，只需要考虑连续合数的情形。关于连续合数，1969年，Grimmtl7】猜想：如果m+l⋯．，m+n是连续合数，那么存在n个不同的素数Pl⋯．，办使得m+jf被PJ(1≤J≤n)整除。这蕴含了n个连续合数的乘积，至少有n个不同的素因子。Grimm证明m>nn一1时，他的猜测成立。1971年，Erd6s和Selfridgetlal利用Halltl9]定理证明m>nn(n)时，Grimm猜测成立。我们利用二项式以及高斯函

5、数的性质证明：当m>兀口如ptlogpnJ时，二项式系数(m：疗l有表示式■山东大学博士学位论文其中aj(1≤i≤n)满足ail(m+O，ai∈N，ai>l，gcd(ai，aj)=1，1si≠Jsn．注意到加’>兀脚p‘logp川，这样，我们细化了Erd6s并[1Selfridge的结果。在算术级数情形，1977年Langevin[27J证明：设n>1，gcd(a，易)=1，如果a+bi(f=1⋯．，n)都不整除兀pg—lptlog一‘n一1Ⅺ，那么存在咒个不同的素数pl⋯．，Pn使得a+by被乃(1≤Jf≤疗)整除。我们进一步证明：设挖>1，ged(a，易)=1，如果口+bi(待1

6、⋯．，万)都不整除兀p1，gcd(ai，aj)=1，1si≠J≤n．这样，我们也细化TLangevin的结果。利用非连续整数情形的w序列我们研究了Goldbach猜想与算术级数的最小素数问题之间的内在关系。1742年，Goldbach猜想每个大于4的偶数2n是两个素数的和。因为下面的情形是平凡的：对于无穷多偶数2p，2p=P+P(其中p是素数)，由此我们给出Goldbach猜想的一个变体：每个大于6的偶数2n是两个不同素数的和。

7、这蕴含了对于大于5的整数n，存在一个自然数r(1≤，sk=n(n—1)一1)使得2n—P，与2n—pl⋯．，2n—P，一1，2n—Pr+1⋯．，2n一肌都互素，其中pl⋯．，肛l，P，，Pr+I⋯．，以是小于n的全体奇素数，而P，满足gcd(p，，厅)=1．也就是说2以一pl，⋯，2n—Pr-I，2n—P，，2n—Pr+l⋯．，2n一肌是一个w序列。令k，Z是满足(七，D=l和lsZsk—l的正整数，记p(k，D为使得P三／(modk)成立的最小素数P，p