1、 毕业设计（论文） 外 文 文 献 翻 译 译文题目： Eulers Theorem and Fermats Theorem 学生姓名： 张云 专 业： 数学与统计学院 指导教师： 张吉刚 2009 年 12 月 30 日 Eulers Theorem and Fermats Theorem Book: Elementary Methods in number theory Author :Melvyn B. Nathanson Page: 7167 PP 2.5 Eulers Theorem and Fermats Theorem Eulers theorem and its corolla
2、ry ,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 cryptogra
3、phy. Theorem2.12（ Euler） Let m be a positive integer, and let a be an integer relatively prime to m .Then ma m mod1 . Proof. Let mrr ,1be a reduced set of residues modulo m .Since 1, ma ， we have mimar i ,11, for 1, , ( )im .Consequently, for every mi ,1 there exists mi ,1 such that mrar ii mo d. Mo
4、reover， mararji mod if and only if ji ， and so is a permutation of the set m,1 and marar ,1 is also a reduced set of residues modulo m .It follows that marararamrrrm m mod2121 mrrrm mod21 mrrrm m o d21 Dividing by mrrr 21， we obtain ma m mod1 This completes the proof. The following corollary is some
5、times called Fermats litter theorem. Theorem 2.13 (Fermat) Let p be a prime number .If the integer a is not divisible by p ,then pa r mod11 Moreover, paa p mod for every integer a . Proof. If p is prime and does not divide a, then 1, pa ， 1 pp ， and paa pp mod11 by Eulers theorem. Multiplying this c
6、ongruence by a ， we obtain paa p mod If p divides a ,then this congruence also holds for a . Let m be a positive integer and let a be an integer that is relatively prime to m .By Eulers theorem, ma m mod1 .The order of a with respect to the modulus m is the smallest positive integer d such that ma d
7、 mod1 .Then md 1 .We shall prove that aordm divides m for every integer a relatively prime top Theorem 2.14 Let m be a positive integer and a an integer relatively prime to m .If d is the order of a modulo m ,then maa lk mod if and only if dlk mod .In particular, ma n mod1 if and only if d divides n
8、 ,and so d divides m . Proof. Since a has order modulo m ,we have ma d mod1 .If dlk mod ， then dqlk ， and so maaaaa lqdldqlk m o d . Conversely, suppose that maa lk mod .By the division algorithm, there exist integers q and r such that rdqlk and 10 dr . Then maaaaaaa rkrqdlrdqlk m o d Since 1, mak ， we can divide this congruence by ka and obtain
