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歐拉定理和費馬定理著作 :初等數(shù)論作者 :Melvyn B. Nathanson頁碼 : P67P712.5歐拉定理和費馬定理歐拉定理及其推論， 費馬定理都是數(shù)論中的重要結(jié)果， 而且在數(shù)學(xué)和計算機領(lǐng)域中都有很多的應(yīng)用 . 在本節(jié)中，我們將可以看到，歐拉定理和費馬定理是如何用來判斷一個正數(shù)是素數(shù)還是合數(shù)以及它們是怎樣應(yīng)用在密碼學(xué)中的.定理 2.12 （歐拉） 設(shè) m 是一個正整數(shù)，d 是一個與

24、 m 互質(zhì)的整數(shù)，則am1 mod m證 明 ： 設(shè)r1,r m是 模 m 的 既 約 剩 余 類 . 由 于a, m1 ， 我 們 可 得ari , m1 i1,m，因此，對于每個i1,m，必存在i1,m使得aririmod m而且，當(dāng)且僅當(dāng) 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 （費馬） 設(shè) p

25、是一個素數(shù)，p 不整除整數(shù) a ，則ar 11 mod p而且，對于每個整數(shù)a ，都有a pa mod p證明： 設(shè) p 是素數(shù)， p 不整除 a ，則 a, p1， pp 1 ，由歐拉定理知a p 1ap1 mod p這個同余類兩邊同乘以a ，我們可得a pa mod p .如果 p 整除 a ，則這個同余式對a 也成立 .設(shè) m 是個正整數(shù)，a 是一個與 m 互質(zhì)的整數(shù) . 由歐拉定理知，am1 mod m ， a 關(guān)于模m 的階是使得a d1 mod m 的最小正整數(shù). 那么 1dm . 我們用 ord m a 來表示 a關(guān)于模 m 的階 . 我們將證明，對于每個與p 互質(zhì)的整數(shù) a ，

26、都有 ord m a 整除m .定理 2.14設(shè) m 是一個正整數(shù)，a 是一個與 m 互質(zhì)的整數(shù) . 如果 d 是模 m 的階，那么當(dāng)且僅當(dāng) kl mod d 有 a kal mod m . 特別地， 當(dāng)且僅當(dāng) d 整除 n ，才有 a n1 mod m ，所以 d 整除m .證 明： 由于 a 關(guān)于模m 的階為d ，即 ad1 mod m . 如果 kl mod d，那 么kldq ，所以a kal dqala dqa l mod m .相反的，假設(shè) a kal mod m. 由除法性質(zhì)得，必存在整數(shù)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假設(shè) an1a(mod m) ，則 d 整除 n ，尤其 d 整除(m) ，根據(jù)歐拉定理可得a (m)1(mod m)例如， m15, a7 , 由于(15)8 ，我們由歐拉定理知781(mod 15)而且， 7 關(guān)于 15 的階是 8 的一個約數(shù) . 我們這樣計算階：717(mod 15)72494(mod 15)732813(mod 15)74911(mod 15)所以7 的階是4 .我們將給出歐拉定理的另一種證明及它

28、的推論. 我們將從關(guān)于群的一些簡單觀察開始. 我們把群的階定義為群的基數(shù)定理2.15 （拉格朗日定理）假設(shè)G 是一個有限群，H 是 G 的子群，則H 的階整除G 的階證明 ：設(shè)G 是一個群，運算為乘法，X 是 G 的一個非空子集. 對于任意aG,我們定義這個集合：aX ax : xX )由 f ( x)ax 定義的映射f : XaX 是一個雙射，所以對于所有的aG ， XaX .假 設(shè) H 是 G 的 子 群 ， 那 么 aH 被稱 作 H 的 一 個 陪 集 . 設(shè) 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 表示陪集 . 假設(shè) G 是一個有限集，則H ， G H 是有限的，及GH G H特別地，我們有H整除G設(shè) G 是一個群， 運算為乘法. 設(shè) aG ， H=a k: kZ，則 1a0HG . 由于對所有的 k ，lZ,ak alak l ，從而可得出H 是 G 的子群 . 這個子群被稱

30、作由a 生成的循環(huán)子群，記作a，循環(huán)子群都是交換的.如果存在一個元素aG，使得 Ga，則群 G 是循環(huán)群 . 此時，元素 a 稱作 G 的生成元 .例如，群 ( Z/7Z )是由 37 Z 生成的階為6 的循環(huán)群 . 同余類 5 7 Z 是這個群的另一個生成元. 如果對于所有整數(shù)kl ，都有 aka l，則由 a 生成的這個循環(huán)群是無限的. 如果存在 k和 l ，使得 k l， a kal ，則 ak l1 .設(shè) d 是最小的正數(shù)，且使得 ad1 ，則這個群的元素 1，a ，a 2 ， ， ad1 是不同的 . 設(shè) nZ ，由除法知， 存在整數(shù) 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 生成的這個循環(huán)群的階為d ，而且，當(dāng)且僅當(dāng)kl (mod d ) ，才有 a kal .設(shè) G 是一個群， aG . 我們可