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

1、毕业设计论文外 文 文 献 翻 译译文题目：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 ,ar

2、e 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.12EulerLet

3、 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 foll

4、ows 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

5、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

6、 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, s

7、uppose 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 ，Eu

8、lers 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 t

9、he 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 f

10、or 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 c

11、oset 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 .T

12、his 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

13、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 su

14、ch 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

15、 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 t

16、he 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. 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 su

17、bgroup 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

18、have ,and so is a positive divisor of .It follows that has order . 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

19、 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 .F

20、or 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 欧拉定理和费马定理欧拉定理及其推论，费马定理都是数论中的重要结果，而且在数学和计算机领域中都有很多的应用.在本节中，我们将可以看到，欧拉定理和费马定理

21、是如何用来判断一个正数是素数还是合数以及它们是怎样应用在密码学中的.定理2.12欧拉设是一个正整数，是一个与互质的整数，那么证明：设是模，我们可得，因此，对于每个，必存在使得而且，当且仅当，所以是集合的排列.也是模的既约剩余类，从而有 两边同除以，我们得 证明完毕.下面的推论有时称作费马小定理定理2.13费马设是一个素数，不整除整数，那么 而且，对于每个整数，都有 证明：设是素数，不整除，那么，由欧拉定理知 这个同余类两边同乘以，我们可得.如果整除，那么这个同余式对也成立.设是个正整数，是一个与互质的整数.由欧拉定理知，关于模的阶是使得.我们用来表示关于模的阶.我们将证明，对于每个与互质的整数

22、，都有整除. 设是一个正整数，是一个与是模的阶，那么当且仅当有.特别地，当且仅当整除，才有，所以整除.证明：由于关于模的阶为，即.如果，那么，所以.相反的，假设.由除法性质得，必存在整数和使得及.那么由于，我们用来整除这个同余类，从而得到由于，是模的阶，那么假设，那么整除，尤其整除，根据欧拉定理可得 例如，,由于，我们由欧拉定理知 而且，关于的阶是的一个约数.我们这样计算阶： 所以的阶是.定理2.15拉格朗日定理假设是一个有限群，是的子群，那么的阶整除的阶证明：设是一个群，运算为乘法，是G,我们定义这个集合：由定义的映射是一个双射，所以对于所有的，.假设是的子群，那么被称作和是子群的陪集.，那么存在，使得，或者，由于是一个子群