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

1、Euler sTheorem and Fermats TheoremBook: Elementary Methods in number theoryAuthor :Melvyn B. NathansonPage: P67P712.5 EulerTheorems and Fermats TheoremEuler s theorem and its corollary ,Fermats theorem ,are fundamental results in number theory ,with many applications in mathematics and computer scie

2、nce .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 ）Letm be a positive integer, and leta be an integer relatively prime tom .Thenam1 mod m .Proof

3、.Let r1 ,r mbe a reduced set of residues modulom .Sincea,m1， we haveari , m1 i1,mfori1,K ,( m) .Consequently, for every i1,mthereexistsi1,msuch thataririmod m .Moreover ， ariar j mod mifand onlyifij ， and sois a permutation of theset 1,mandar1 ,ar mis also a reduced set of residues modulom .It follo

4、wsthatam r1r2 r mar1ar2ar mmod mr 1 r2rmmod mr1 r2r mmod mDividing byr1r2r m ， we obtainam1 mod mThis completes the proof.The following corollary is sometimes called Fermats litter theorem.Theorem 2.13 (Fermat) Letp be a prime number .If the integer a is not divisible byp ,thena r 11 mod pMoreover,a

5、 pa mod pfor every integera .Proof . Ifp is prime and does not divide a, thena, p1 ，pp1 ， anda p 1apby Euler s theorem. Multiplying this congruence by1 mod pa ， we obtaina pa mod pIfp divides a ,then this congruence also holds fora .Letm be a positive integer and leta be an integer that is relativel

6、y prime tom .By Eulerstheorem, am1 mod m.The order ofa withrespect tothe modulusm is the smallestpositiveintegerdsuchthata d1 mod m.Then1dm.We shallprovethatord madividesmfor every integera relatively prime topTheorem 2.14Letmbe a positiveinteger andaan integer relatively primetom .Ifdisthe order of

7、amodulom ,thena ka lmod mif and only ifkl mod d.In particular,a n1 mod mif and only ifddividesn ,and sod dividesm.Proof.Sinceahas ordermodulom ,we havea d1 mod m.Ifkl mod d， thenk l dq ， and soa ka lala dqdqa l mod m .Conversely, suppose thatakalmod m .By the division algorithm, there exist integers

8、 q andr such thatkldqr and0rd1.Thena kal dqrala d qa ra k a rmod mSince a k ,m1， we can divide this congruence bya kand obtainar1 mod mSince0rd1distheorder ofamodulom,itfollowsthatr0,and so， andkl mod d .Ifa n1a(mod m)， thenddividesn.Inparticular,d divides(m) ， sincea (m )1(mod m)by Euler s theorem.

9、For example; letm15and a=7.Since(15)8 ，Euler s theorem tells us that781(mod 15)Moreover, the order of7with respect to15 is a divisor of8. We can compute the order asfollows:717(mod 15)72494(mod 15)732813(mod 15)74911(mod 15)And so the order of7is 4 .We shall give a second proof of Euler s theorem an

10、d its corollaries .we begin with some simpleobservations about groups. We define the order of a group as the cardinality of the group.Theorem2.15 (Lagrange s theorem)IfG isa finite groupand H isa subgroup of G ,then the order ofHdivides the order ofGProof.Let G beagroup,writtenmultiplicatively,and l

11、etX beanonemptysubset ofG .For everyaG ,we define the setaX ax : xX )The mapf : XaXdefinedbyf (x)axis abijection,andsoXaXfor allaG .IfH is subgroup of G , thenaHis called a coset ofH . Let aHandbHbe cosetsofthe subgroupH 。 If aHbH,thenthereexistx, yH such that axby ，or ,sinceHis a subgroup, baxy 1az

12、 ，wherezxy 1H 。Thenbhazhah forallhH and sobHaH .Bysymmetry,aHbH ,andsoaHbH .Therefore ,cosets of a subgroup H are either disjoint or equal .Since every element ofG belongs to somecoset ofH （ for example ,aaHfor allaG）， it follows that the cosets ofHpartitionG .Wedenote the set of cosets byG H .IfG i

13、s a finite group, then Hand G H arefinite ,andGH G HIn particular, we see thatH divides G .LetGbeagroup,writtenmultiplicatively,and letaG .Let H ak : kz.Then1a0HG Sinceakalak lforall k,lZ it followsthatH is a subgroup ofG .Thissubgroupiscalledthecyclic subgroupgeneratedby a ,andwrittena .Cyclicsubgr

14、oups are abelian.Thegroup G is cyclicifthereexistsan elementaG such thatGa .Inthiscases ,the elementais called a generator ofG For example, the groupZ 7Zis a cyclicgroup of order 6 generated by37Z .The congruence class 57Z is another generator of thisgroup.If akalforallintegerskl then the cyclic sub

15、group generated byaisinfinite .Ifthere exist integers k and lsuch thatklandaka l thenak l1 . Letdbe thesmallest positive integer such thatad1.Then the group elements 1a a2a d1aredistinct .LetnZ .Bythedivisionalgorithm,thereexist integersq andrsuchthatndqrand 0rd1 Asa nadq ra dqara rit follows thataa

16、 n : n Zar : 0 r d 1andthe cyclicsubgroupgenerated bya has order d .Moreover aka lifand only ifkl (mod d )LetG be a group, and letaG .we define the order ofaas the cardinality of the cyclicsubgroup generated byaTheorem 2.16 LetGbe a finite group, and a G .Then the order of the element a dividesthe o

17、rder of the group G .a is the order of theProof. This follows immediately from Theorem 2.15, since the order ofcyclic subgroup thata generates.Let us apply these remarks to the special case whenGZ mZ is the group of units inthe ringofcongruence classes modulom .Then G is afinite groupof orderm .Leta

18、, m1and letd be the order ofamz in G ,that is the order of the cyclic subgroupgenerated by a mz .By Theorem 2.16, ddividesm ， and sommdmamZ a mZd1mZ .amZEquivalently,am1 mod m ，This is Euler s theorem.Theorem 2.17 Let G be a cyclic group of order m ,and let H be a subgroup of G .If a is a generator

19、of G ,then there exists a unique divisor d of m such that H is the cyclic subgroupgenerated by a d ,and H has order m.dProof .Let Sbethesetofallintegersu suchthat a uH .Ifu,v S ,thena u ，a vH .SinceHis asubgroup,itfollowsthatau ava u vHandau a v1a u vH Therefore,uvS,andS is a subgroup ofZ .ByTheorem

20、 1.3,there is a uniquenonnegative integerd suchthatSdZ ,andsoHisthe cyclicsubgroupgeneratedby a d .Sincea m1H ,we havemS ,and sod is a positive divisor ofm .It follows thatHhas ordermd .Theorem 2.18LetG be a cyclic group of orderm ,and let abe a generator ofG .For everyintegerk ,the cyclic subgroupg

21、eneratedbya khasordermd,wheredm, k,anda kad.In particular,G has exactlym generators.Proof. Sincedk , m ,there exist integersxandy such thatdkxmy .Thendakxmyakxm yakxaaand soa da kanda ka d.Sinceddividesk ,there existsaninteger zsuchthatkdz .Thenaka dz，andsoa kadandakad.Therefore,a ka dand a khas ord

22、ermd.Inparticularak generates Gifand onlyifd 1if andonly ifm, k1 ,and soGhasexactlym generators .This completes the proof.We can now give a group theoretic proof order m .For every divisor d of m ,the groupofTheorem 2.8.LetGbe a cyclic groupofG has a unique cyclic subgroup of orderd ,andthis subgrou

23、p has exactly( d )generators .Since every element ofGgenerates a cyclicsubgroup ,it follows thatmd .d m欧拉定理和费马定理著作 :初等数论作者 :Melvyn B. Nathanson页码 : P67P712.5欧拉定理和费马定理欧拉定理及其推论， 费马定理都是数论中的重要结果， 而且在数学和计算机领域中都有很多的应用 . 在本节中，我们将可以看到，欧拉定理和费马定理是如何用来判断一个正数是素数还是合数以及它们是怎样应用在密码学中的.定理 2.12 （欧拉） 设 m 是一个正整数，d 是一个与

24、 m 互质的整数，则am1 mod m证 明 ： 设r1,r m是 模 m 的 既 约 剩 余 类 . 由 于a, m1 ， 我 们 可 得ari , m1 i1,m，因此，对于每个i1,m，必存在i1,m使得aririmod m而且，当且仅当 ij ，ariar j mod m ，所以是集合1,m的排列 .ar1 ,ar m也是模 m 的既约剩余类，从而有am r1 r2 K rmar1ar2 Lar mmod mr 1 r 2rmmod mr1r2rmmod m两边同除以 r1r2 rm ，我们得a m1 mod m证明完毕 .下面的推论有时称作费马小定理定理 2.13 （费马） 设 p

25、是一个素数，p 不整除整数 a ，则ar 11 mod p而且，对于每个整数a ，都有a pa mod p证明： 设 p 是素数， p 不整除 a ，则 a, p1， pp 1 ，由欧拉定理知a p 1ap1 mod p这个同余类两边同乘以a ，我们可得a pa mod p .如果 p 整除 a ，则这个同余式对a 也成立 .设 m 是个正整数，a 是一个与 m 互质的整数 . 由欧拉定理知，am1 mod m ， a 关于模m 的阶是使得a d1 mod m 的最小正整数. 那么 1dm . 我们用 ord m a 来表示 a关于模 m 的阶 . 我们将证明，对于每个与p 互质的整数 a ，

26、都有 ord m a 整除m .定理 2.14设 m 是一个正整数，a 是一个与 m 互质的整数 . 如果 d 是模 m 的阶，那么当且仅当 kl mod d 有 a kal mod m . 特别地， 当且仅当 d 整除 n ，才有 a n1 mod m ，所以 d 整除m .证 明： 由于 a 关于模m 的阶为d ，即 ad1 mod m . 如果 kl mod d，那 么kldq ，所以a kal dqala dqa l mod m .相反的，假设 a kal mod m. 由除法性质得，必存在整数q 和 r 使得kldqr 及 0r d1.那么a ka l dq ra ladqak a

27、rmod ma r由于 a k , m1，我们用 a k来整除这个同余类，从而得到a r1 mod m由于0 rd，d是模 m 的阶，那么 r 0, k 1(mod d )1假设 an1a(mod m) ，则 d 整除 n ，尤其 d 整除(m) ，根据欧拉定理可得a (m)1(mod m)例如， m15, a7 , 由于(15)8 ，我们由欧拉定理知781(mod 15)而且， 7 关于 15 的阶是 8 的一个约数 . 我们这样计算阶：717(mod 15)72494(mod 15)732813(mod 15)74911(mod 15)所以7 的阶是4 .我们将给出欧拉定理的另一种证明及它

28、的推论. 我们将从关于群的一些简单观察开始. 我们把群的阶定义为群的基数定理2.15 （拉格朗日定理）假设G 是一个有限群，H 是 G 的子群，则H 的阶整除G 的阶证明 ：设G 是一个群，运算为乘法，X 是 G 的一个非空子集. 对于任意aG,我们定义这个集合：aX ax : xX )由 f ( x)ax 定义的映射f : XaX 是一个双射，所以对于所有的aG ， XaX .假 设 H 是 G 的 子 群 ， 那 么 aH 被称 作 H 的 一 个 陪 集 . 设 aH 和 bH 是 子 群 H 的 陪集 . aH bH， 则 存 在 x, yH ， 使 得 axby ， 或者 ， 由 于

29、 H 是一 个 子 群 ，b axy1az，这里 z xy 1H . 对于所有的h，所以bHaH；H bh azh ah同理，aHbH , 所以 aHbH 因此子群 H 的陪集不交或相等. 由于 G 的每个元素属于H 的陪集（例如，对于所有的aG 都有 aaH ），从而可得出H 划分 G 的陪集 . 我们用G H 表示陪集 . 假设 G 是一个有限集，则H ， G H 是有限的，及GH G H特别地，我们有H整除G设 G 是一个群， 运算为乘法. 设 aG ， H=a k: kZ，则 1a0HG . 由于对所有的 k ，lZ,ak alak l ，从而可得出H 是 G 的子群 . 这个子群被称

30、作由a 生成的循环子群，记作a，循环子群都是交换的.如果存在一个元素aG，使得 Ga，则群 G 是循环群 . 此时，元素 a 称作 G 的生成元 .例如，群 ( Z/7Z )是由 37 Z 生成的阶为6 的循环群 . 同余类 5 7 Z 是这个群的另一个生成元. 如果对于所有整数kl ，都有 aka l，则由 a 生成的这个循环群是无限的. 如果存在 k和 l ，使得 k l， a kal ，则 ak l1 .设 d 是最小的正数，且使得 ad1 ，则这个群的元素 1，a ，a 2 ， ， ad1 是不同的 . 设 nZ ，由除法知， 存在整数 q 和 r ，使得 n dq r ，0 r d 1 . 由于ana dq ra dqa r ，a r从而有aa n : n Zar : 0 r d 1 ，由 a 生成的这个循环群的阶为d ，而且，当且仅当kl (mod d ) ，才有 a kal .设 G 是一个群， aG . 我们可