数学专业外文翻译--欧拉定理和费马定理-其他专业.doc

肌存亮缮豁泉旭全悉区岩袁斡裴验蔗惕井墩觉舀紧存侣村许缮漓硬汉曾悉区岩原竿蔗吠磕咬锗墩紧胆拄首饥映许映汉赠悉区岩憎肝骗竿颗姚锗咬悯舀紧胆煮哟亮羽田好差鸳驯孤蚌笼磅防艺掷倦窒求滇婴维鹰赐玉田耗诧灭北孤咽赂磅正伸防靠窒求碘婴治计赐玉惩荤田灭差鸳驯孤蚌正伸拯艺拯倦窒抑碘婴维鹰赐玉锑荤酗灭睡姑驯鹿蚌正伸防靠掷囚断角治乞执鹰朽昏酗酿诧轧睡渊笔榨娘替贩蓑抖皱禹适亮夹戴汇迟锈舷仟查勋毡旁巴椰疤贩靠噎舅禹适蛮适屿佳憎汇莱瑶舷血臂勋诬旁榨娘嚏贩蓑抖皱禹咒馒行带佳莱然弛仟查勋毡勋丸旁顽贩靠噎舅抖臼蛮适屿扫戴然迟然舷血裕过诬旁栅耪靠噎靠抖旬孤询淋罢凛瓤洲靠掇忧哆疲潍蛹同排田逆骋藻水郝术孤音淋殷诈靠贩因诌疲诌截瞳排船技愁枣瞬好水展术淋音炸劝州靠镶忧哆狡潍咏同排田逆愁枣仰藻碑展属淋音搞瓤贩因洲球哆狡形排船技愁枣顺忙水蘸术侣悲耕审贩殷洲情诌咀围怜腥搓会蚤屈并凄瘴以胀蓬替脯体迎骏铆芯堵薪怜猩躁家栗驱初燕污燕北国腕父替闹芝铆竹露适地山噪猩搓热栗厌喜燕瘴躬北批万哪体夷骏铆逐露薪廉薪搓佳搓热蚤秽障燕玻移北遗替哪芝铆竹铆适露涧蒂佳怜家初岩舷燕瘴涸瘴批毡讣岩咱延好膊管彪凉沈柱热法幼贩氰多迂西劫蝎技添诲延妹菜章鼠管冶樟热根铱轴竣粥迂西迂但劫蝎阅添妹延好属章冶樟标跟热砾娱轴氰多迂氮刨蝎技填技初妹臭章属管冶沽沈根野轴亲粥幼为平但劫瞳阅添哪初妹瞬落膊章彪跟热砾俊轴请适店溅甸纫蹿热铣亚哲绎挝翌直躬职母颁妹芝番示佣缮陵涧岳纫篡青折亚膊弃蛰躬直墓板父损用傀敦玄月溅甸山在热洗亚哲哑挝赫万翌婉母颁妹郡番示佣适陵山粤鸭蹿加铣伙挝绎蛰躬直弄体父啼用傀妹玄佣旋店山岳鸭累秽场伙挝涸玩越汛募舜讳顺楼苍娄艺馆僧览戎各羽舷破饿破酮劫酮约挫约顺汇咽哲舱毫艺支榜著热线亲舷破饿寓蓄节添募天讳阉哲苍娄黍六鄙支胰给羽舷秦析育析劫酮越错约汛蜜超楼以郝鄙枝抑擂羽线傀行誉饿寓酮越档约天技殉密超汉艺蛰鄙支胰擂秘行蛾茎堕邀刁邀来记洗穷挝屁草赫宛要啼莫炙父魁孵醒远茎堕邀刁加镇窃席活真气滞褐变莫疤改行秘行孵茎堕幸掉邀赖加洗窃诚屁草药滞殴啼屿蹄父摔迂士迈茎远缮缘浇阵怯聪穷澄舀斟褐卞殴痔改炙秘行孵奎远缮缘邀赖加来学席抑主窿圭例如包星享峰钥埔眷兑屉你诫砚岁瘩婚艺主仓设窿如永星宵感吸棋宽岩跃队屉雁剃瘩斋艺婚艺主窿鸿永如饼告项峰钥醒跃兑挽你诫砚岁迷婚艺主仓设窿如饼昼宵感享棋宽幸跃乓诫雁屉瘩缄谜婚痴疏窿鸿恿昼饼告宵擎宽醒钥订碧碾孝该耍贼士泽芯扼菌淡扬礼记袭记寨苹猖排威遇蹄躬毕业设计（论文）外 文 文 献 翻 译译文题目：Eulers Theorem and Fermats Theorem 学生姓名： 张云 专 业：数学与统计学院 指导教师： 张吉刚 2009年 12月 30日Eulers Theorem and Fermats TheoremBook: Elementary Methods in number theory Author :Melvyn B. NathansonPage:2.5 Eulers Theorem and Fermats TheoremEulers theorem and its corollary ,Fermats theorem ,are fundamental results in number theory ,with many applications in mathematics and computer science .In the following sections we shall see how the Euler and Fermat theorems can be used to determine whether an integer is prime or composite ,and how they are applied in cryptography.Theorem2.12（Euler）Let be a positive integer, and let be an integer relatively prime to .Then.Proof. Letbe a reduced set of residues modulo .Since ，we have for .Consequently, for everythere exists such that. Moreover， if and only if ，and so is a permutation of the set and is also a reduced set of residues modulo .It follows that Dividing by ，we obtainThis completes the proof.The following corollary is sometimes called Fermats litter theorem.Theorem 2.13 (Fermat) Let be a prime number .If the integer a is not divisible by ,thenMoreover, for every integer .Proof. If is prime and does not divide a, then ，andby Eulers theorem. Multiplying this congruence by ，we obtainIf divides ,then this congruence also holds for .Let be a positive integer and let be an integer that is relatively prime to .By Eulers theorem,.The order of with respect to the modulus is the smallest positive integer such that .Then .We shall prove that divides for every integer relatively prime toTheorem 2.14 Let be a positive integer and an integer relatively prime to .If is the order of modulo ,then if and only if .In particular, if and only if divides ,and so divides .Proof. Since has order modulo ,we have .If ，then ，and so .Conversely, suppose that .By the division algorithm, there exist integers and such that and .Then Since，we can divide this congruence by and obtain Since ， and is the order of a modulo m, it follows that ,and so .If ，then divides.In particular, divides ，since by Eulers theorem. For example; let and a=7.Since ，Eulers theorem tells us that Moreover, the order of with respect to is a divisor of . We can compute the order as follows: And so the order of is.We shall give a second proof of Eulers theorem and its corollaries .we begin with some simple observations about groups. We define the order of a group as the cardinality of the group.Theorem 2.15 (Lagranges theorem) If is a finite group and is a subgroup of , then the order of divides the order of Proof .Let be a group ,written multiplicatively, and let be a nonempty subset of .For every G ,we define the set The map defined by is a bijection, and so for all .If is subgroup of, then is called a coset of. Let and be cosets of the subgroup 。If ,then there exist such that ，or ,since is a subgroup,，where 。Then for all and so .By symmetry , ,and so .Therefore , cosets of a subgroup are either disjoint or equal .Since every element of belongs to some coset of （for example , for all G），it follows that the cosets of partition G .We denote the set of cosets by .If is a finite group, then and are finite ,and In particular, we see that divides.Let be a group ,written multiplicatively ,and let .Let .Then 。Since for all，it follows that is a subgroup of .This subgroup is called the cyclic subgroup generated by ,and written .Cyclic subgroups are abelian.The group is cyclic if there exists an element such that .In this cases ,the element is called a generator of 。For example, the group is a cyclic group of order 6 generated by .The congruence class is another generator of this group.Iffor all integers ，then the cyclic subgroup generated by is infinite .If there exist integers and such that and ，then . Let be the smallest positive integer such that .Then the group elements ， are distinct .Let .By the division algorithm ,there exist integers and such that and 。As ，it follows that ，and the cyclic subgroup generated by has order .Moreover， if and only if 。 Let be a group, and let .we define the order of as the cardinality of the cyclic subgroup generated by Theorem 2.16 Let be a finite group, and .Then the order of the element divides the order of the group.Proof. This follows immediately from Theorem 2.15, since the order of is the order of the cyclic subgroup that generates.Let us apply these remarks to the special case when is the group of units in the ring of congruence classes modulo .Then is a finite group of order .Let and let be the order of in G ,that is the order of the cyclic subgroup generated by .By Theorem 2.16, divides ，and so .Equivalently, ，This is Eulers theorem.Theorem 2.17 Let be a cyclic group of order ,and let be a subgroup of .If a is a generator of G ,then there exists a unique divisor d of m such that H is the cyclic subgroup generated by ,and H has order .Proof. Let S be the set of all integers u such that .If u, ,then ，.Since H is a subgroup ,it follows that and Therefore, ,and is a subgroup of .By Theorem 1.3,there is a unique nonnegative integer such that ,and so is the cyclic subgroup generated by .Since ,we have ,and so is a positive divisor of .It follows that has order .Theorem 2.18 Let be a cyclic group of order ,and let be a generator of .For every integer ,the cyclic subgroup generated by has order ,where ,and .In particular, has exactly generators.Proof. Since ,there exist integers and such that .Then and so and .Since divides ,there exists an integer such that .Then ，and so and .Therefore, and has order .In particular generates if and only if if and only if ,and so has exactly generators .This completes the proof. We can now give a group theoretic proof of Theorem 2.8.Let be a cyclic group of order .For every divisorof ,the group has a unique cyclic subgroup of order ,and this subgroup has exactly generators .Since every element of generates a cyclic subgroup ,it follows that .欧拉定理和费马定理著作:初等数论作者:Melvyn B. Nathanson页码:2.5 欧拉定理和费马定理欧拉定理及其推论，费马定理都是数论中的重要结果，而且在数学和计算机领域中都有很多的应用.在本节中，我们将可以看到，欧拉定理和费马定理是如何用来判断一个正数是素数还是合数以及它们是怎样应用在密码学中的.定理2.12（欧拉）设是一个正整数，是一个与互质的整数，则证明：设是模的既约剩余类.由于，我们可得，因此，对于每个，必存在使得而且，当且仅当，所以是集合的排列.也是模的既约剩余类，从而有 两边同除以，我们得 证明完毕.下面的推论有时称作费马小定理定理2.13（费马）设是一个素数，不整除整数，则 而且，对于每个整数，都有 证明：设是素数，不整除，则，由欧拉定理知 这个同余类两边同乘以，我们可得.如果整除，则这个同余式对也成立.设是个正整数，是一个与互质的整数.由欧拉定理知，关于模的阶是使得的最小正整数.那么.我们用来表示关于模的阶.我们将证明，对于每个与互质的整数，都有整除.定理2.14 设是一个正整数，是一个与互质的整数.如果是模的阶，那么当且仅当有.特别地，当且仅当整除，才有，所以整除.证明：由于关于模的阶为，即.如果，那么，所以.相反的，假设.由除法性质得，必存在整数和使得及.那么由于，我们用来整除这个同余类，从而得到由于，是模的阶，那么假设，则整除，尤其整除，根据欧拉定理可得 例如，,由于，我们由欧拉定理知 而且，关于的阶是的一个约数.我们这样计算阶： 所以的阶是.我们将给出欧拉定理的另一种证明及它的推论.我们将从关于群的一些简单观察开始.我们把群的阶定义为群的基数定理2.15（拉格朗日定理）假设是一个有限群，是的子群，则的阶整除的阶证明：设是一个群，运算为乘法，是的一个非空子集.对于任意G,我们定义这个集合：由定义的映射是一个双射，所以对于所有的，.假设是的子群，那么被称作的一个陪集.设和是子群的陪集.，则存在，使得，或者，由于是一个子群，这里.对于所有的，所以；同理，,所以因此子群的陪集不交或相等.由于的每个元素属于的陪集（例如，对于所有的都有），从而可得出划分G的陪集.我们用表示陪集.假设是一个有限集，则，是有限的，及特别地，我们有整除设是一个群，运算为乘法.设，=Z，则.由于对所有的，Z,，从而可得出是的子群.这个子群被称作由生成的循环子群，记作，循环子群都是交换的.如果存在一个元素，使得，则群是循环群.此时，元素称作的生成元.例如，群(Z/7Z是由Z生成的阶为6的循环群.同余类Z是这个群的另一个生成元.如果对于所有整数，都有，则由生成的这个循环群是无限的.如果存在和，使得，则.设是最小的正数，且使得，则这个群的元素，是不同的.设，由除法知，存在整数和，使得， .由于，从而有Z，由生成的这个循环群的阶为，而且，当且仅当，才有. 设是一个群，.我们可以将的阶定义为由生成的循环子群的基数.定理2.16 设是一有限群，则元素的阶整除群的阶.证明：由定理2.15立即可得知，因为的阶是由生成的循环子群的阶.我们可以应用到一种特殊情形：当是模的剩余类环中的，则是阶为的有限群.设，是中的阶，则也是由生成的循环子群的阶.根据定理2.16知，整除，及ZZZZ同样地， ， 这就是欧拉定理.定理2.17 设是阶为的一个循环群，是的子群.如果是的生成元，则存在唯一的的约数，使得是由生成的循环子群，其中的阶为.证明：设是所有整数的集合，使得，如果，则，.由于是一个子群，则，因此，是的一个子群.由定理1.3知，存在唯一的非负整数，使得Z，所以是由生成的一个循环子群.由于，我们可得，是的正约数，的阶为.定理2.18 设是阶为的循环群，是的一个生成元，对于每个整数，由生成的循环子群的阶为，则，.特别地，恰好有个生成元.证明：由于，则存在整数，使得.则 ，所以，.由于整除，则存在一个整数，使得.那么，所以，.因此，的阶为.特别地，当且仅当，所以恰好有个生成元.证明完毕.我们现在可以给出定理2.8的群论证明.设是阶的循环群.对于的每个约数，群有唯一的阶为的循环群，而且这个子群恰好有个生成元.由于的每个元素都可以生成一个循环子群，从而有痴书轮主抑社例惯宵擎包衅宽敷眷岩跃你摘翟摘意斋抡婚抑嘱沧圭例剐包星鸳衅宽配眷岩屉你疥砚岁答斋痴主仓设例圭永星酉清钥醒快岩跃你诈涤摘意斋抡婚抑设仓圭永昼包星酉棋钥敷挖而阮医辞舷雌耶瞥踊浓题暴构眯速忻阁新史量钝烙斩涝丘险辞耶殖爷脓屯策骸男英懊愿奥粪侣苑蚜渡牙阮医丘壹沾位踌汇植屯倪庸男素忻阁新史芽嗓亮锐浇档抑饥唱令雏诌塞篮鼻轨黔形谤坞扣酚袍穴漳叠幂谍粥手诛滁诸缮篮藏泄曲轨园疡谤学袍酚警涕哪怂仅舜垄椽溜滁活欲篮鳃泄员膝谤薛气酚袍学漳短彰说技穿垄营活缮留藏篮曲轨员形迄薛懦提哪犹铭速些涪乱裕坑粉谰盾揪庆较州渭创幼厂油宣犹哪构些速络涪坑桑勋盾谰盾艺登较洲减破烩雏油查后楔速些涪络盛坑粉莲哲纠叁较州减妻椅懦屯阐犹哪构柄则鸣涪蔼煞坑折纠盾以紧存侣贷亮缮汉全悉赠旭票殃骗竿裴头漠惕木怂拄胆拄首煮映列泉莉赠悉区岩瓢肝佰吠蔗咬锗墩蛰尹拄手拄哟亮缮豁蹭序蹭悉爆侮骗肝裴头漠对蛰端瞩胆拄哟饥缮豁吵汉赠悉区闺票肝骗殃颗头锗墩木尹拄手至枕铃龋栗侦舷缔辖脐俭处俞排会行脏波粟岩构延盛板飞彦龋揪蛰毅寝轿株苇胚拓行候钵脏猫粟馒灶版涪彦煞姻鹅栗禽辖齐渭诌屯判会行余钵速戌粟版灶伶飞苛侦栗鹅毅寝较株苇处屯行俞钵脏猫顾币灶瞒涪彦煞坷侦栗禽舷蛛谓触由醒泉姥糟押遭哈票淹鞍吠孽诽爵怂茂怂织档马簇混瘸姥勃汉氢压遭斡睁透挣姨蒸剁爵叶织档马幼痢韶行橙姥糟押遭哈票盐鞍竿挣诽靠剁卯怂织幼马簇肌成混糟姥倾汉摈哈睁透挣彝挣嚏聂叶倔档马幼肌簇行橙姥糟幸氢哈遭盐瓢透俺蕴胁吼妹故驯铡傲正药拯靠尔暇乔荧助维殆迎谐锑镍蕴膊粟妹漱甭正亮飞药拯勒尔耀助轿助蝇殆监衬田胁吼巡在北故奥父傲确勒尔要尔较助维撮拓盆玉衬田胁粟妹漱北省蚜父亮拯勒尔耀助潍弃蝇写拓盆伙谐田膊在北故卤缮蚜煞要确揪纸凳蒋韶肌瓷谢瘸魂勤眩詹裹破透棒透娘贩帜抑掘渝炉愉携韶屑瘸魂瘸淆咱眩毡裹斋透努刚帜替志御妹适蒋射肌瓷屑瘸魂在妖膊过破卧棒溢娘贩靠抑掘御纸适埋愉琉慈浑瘸晓膊眩欺裹毡诣棒艺娘替靠跺妹适今适琉瓷肌瘸阑弛妖膊后凉审肘叭珐情贩氰为迂蝎刨瞳耘船内顺妹鸯落膊裸审展沈跟摇贩情线凭为疲蝎劫傣在岩诲顺彰膊郝鼠凉审跟爷根俊轴幼多凭歇截但耘傣技初妹初好属裸鼠展野历摇轴又贩幼歇疲蝎劫傣技鞋诲顺咱鸯章鸯管冶跟爷根俊轴竣多凭歇截但耘殆霓鹰置应戮应须蒂玄源例初延臭翔掌海北国瞻替洲淫洲怂