數(shù)學(xué)專業(yè)外文翻譯--歐拉定理和費馬定理

1、<p><b>　　畢業(yè)設(shè)計（論文）</b></p><p>　　外 文 文 獻(xiàn) 翻 譯</p><p>　　譯文題目：Euler’s Theorem and Fermat’s Theorem </p><p>　　學(xué)生姓名： 張云 </p><p>　　專 業(yè)：數(shù)學(xué)與統(tǒng)計學(xué)院 <

2、;/p><p>　　指導(dǎo)教師： 張吉剛 </p><p>　　2009年 12月 30日</p><p>　　Euler’s Theorem and Fermat’s Theorem</p><p>　　Book: Elementary Methods in number theory </p><p&

3、gt;　　Author :Melvyn B. Nathanson</p><p><b>　　Page:</b></p><p>　　2.5 Euler’s Theorem and Fermat’s Theorem</p><p>　　Euler’s theorem and its corollary ,Fermat’s theorem ,ar

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

5、prime or composite ,and how they are applied in cryptography.</p><p>　　Theorem2.12（Euler）Let be a positive integer, and let be an integer relatively prime to .Then</p><p><b>　　.</b>

6、</p><p>　　Proof. Letbe a reduced set of residues modulo .Since ，we have for .Consequently, for everythere exists such that</p><p><b>　　.</b></p><p>　　Moreover， if and o

7、nly if ，and so is a permutation of the set and is also a reduced set of residues modulo .It follows that </p><p>　　Dividing by ，we obtain</p><p>　　This completes the proof.</p><p&g

8、t;　　The following corollary is sometimes called Fermat’s litter theorem.</p><p>　　Theorem 2.13 (Fermat) Let be a prime number .If the integer a is not divisible by ,then</p><p><b>　　Moreov

9、er,</b></p><p>　　for every integer .</p><p>　　Proof. If is prime and does not divide a, then ，，and</p><p>　　by Euler’s theorem. Multiplying this congruence by ，we obtain</

10、p><p>　　If divides ,then this congruence also holds for .</p><p>　　Let be a positive integer and let be an integer that is relatively prime to .By Euler’s theorem,.The order of with respect to the

11、 modulus is the smallest positive integer such that .Then .We shall prove that divides for every integer relatively prime to</p><p>　　Theorem 2.14 Let be a positive integer and an integer relatively pri

12、me to .If is the order of modulo ,then if and only if .In particular, if and only if divides ,and so divides .</p><p>　　Proof. Since has order modulo ,we have .If ，then ，and so </p><p>&l

13、t;b>　　.</b></p><p>　　Conversely, suppose that .By the division algorithm, there exist integers and such that </p><p><b>　　and .</b></p><p><b>　　Then</

14、b></p><p>　　Since，we can divide this congruence by and obtain</p><p>　　Since ， and is the order of a modulo m, it follows that ,and so .</p><p>　　If ，then divides.In particula

15、r, divides ，since by Euler’s theorem.</p><p>　　For example; let and a=7.Since ，Euler’s theorem tells us that </p><p>　　Moreover, the order of with respect to is a divisor of . We can compute

16、the order as follows:</p><p>　　And so the order of is.</p><p>　　We shall give a second proof of Euler’s theorem and its corollaries .we begin with some simple observations about groups. We defi

17、ne the order of a group as the cardinality of the group.</p><p>　　Theorem 2.15 (Lagrange’s theorem) If is a finite group and is a subgroup of , then the order of divides the order of </p><p>

18、　　Proof .Let be a group ,written multiplicatively, and let be a nonempty subset of .For every G ,we define the set </p><p>　　The map defined by is a bijection, and so for all .If is subgroup of, then i

19、s 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 disjoi

20、nt 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 ar</p><p>

21、;　　In particular, we see that divides.</p><p>　　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 gen

22、erated by ,and written .Cyclic subgroups are abelian.</p><p>　　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 cy

23、clic group of order 6 generated by .The congruence class is another generator of this group.</p><p>　　Iffor all integers ，then the cyclic subgroup generated by is infinite .If there exist integers and such

24、 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 ，</p><p>　　it fol

25、lows that </p><p><b>　　，</b></p><p>　　and the cyclic subgroup generated by has order .Moreover， if and only if 。</p><p>　　Let be a group, and let .we define the order

26、 of as the cardinality of the cyclic subgroup generated by </p><p>　　Theorem 2.16 Let be a finite group, and .Then the order of the element divides the order of the group.</p><p>　　Proof. Thi

27、s follows immediately from Theorem 2.15, since the order of is the order of the cyclic subgroup that generates.</p><p>　　Let us apply these remarks to the special case when is the group of units in the rin

28、g 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 </p><p><b>

29、;　　.</b></p><p>　　Equivalently,</p><p><b>　　，</b></p><p>　　This is Euler’s theorem.</p><p>　　Theorem 2.17 Let be a cyclic group of order ,and let be a

30、 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 .</p><p>　　Proof. Let S be the set of all integers u such th

31、at .If u, ,then ，.Since </p><p>　　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 gen

32、erated by .Since ,we have ,and so is a positive divisor of .It follows that has order .</p><p>　　Theorem 2.18 Let be a cyclic group of order ,and let be a generator of .For every integer ,the cyclic subgro

33、up generated by has order ,where ,and .In particular, has exactly generators.</p><p>　　Proof. Since ,there exist integers and such that .Then </p><p>　　and so and .Since divides ,there ex

34、ists an integer such that .Then </p><p><b>　　，</b></p><p>　　and so and .Therefore, and has order .In particular generates if and only if if and only if ,and so has exactly gene

35、rators .This completes the proof. </p><p>　　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

36、this subgroup has exactly generators .Since every element of generates a cyclic subgroup ,it follows that </p><p><b>　　.</b></p><p><b>　　歐拉定理和費馬定理</b></p><p&

37、gt;<b>　　著作:初等數(shù)論</b></p><p>　　作者:Melvyn B. Nathanson</p><p><b>　　頁碼:</b></p><p>　　2.5 歐拉定理和費馬定理</p><p>　　歐拉定理及其推論，費馬定理都是數(shù)論中的重要結(jié)果，而且在數(shù)學(xué)和計算機領(lǐng)域中都有很多

38、的應(yīng)用.在本節(jié)中，我們將可以看到，歐拉定理和費馬定理是如何用來判斷一個正數(shù)是素數(shù)還是合數(shù)以及它們是怎樣應(yīng)用在密碼學(xué)中的.</p><p>　　定理2.12（歐拉）設(shè)是一個正整數(shù)，是一個與互質(zhì)的整數(shù)，則</p><p>　　證明：設(shè)是模的既約剩余類.由于，我們可得，因此，對于每個，必存在使得</p><p>　　而且，當(dāng)且僅當(dāng)，，所以是集合的排列.也是模的既約剩余類，

39、從而有</p><p><b>　　兩邊同除以，我們得</b></p><p><b>　　證明完畢.</b></p><p>　　下面的推論有時稱作費馬小定理</p><p>　　定理2.13（費馬）設(shè)是一個素數(shù)，不整除整數(shù)，則</p><p>　　而且，對于每個整數(shù)，都有

40、</p><p>　　證明：設(shè)是素數(shù)，不整除，則，，由歐拉定理知</p><p>　　這個同余類兩邊同乘以，我們可得</p><p><b>　　.</b></p><p>　　如果整除，則這個同余式對也成立.</p><p>　　設(shè)是個正整數(shù)，是一個與互質(zhì)的整數(shù).由歐拉定理知，，關(guān)于模的階是使得

41、的最小正整數(shù).那么.我們用來表示關(guān)于模的階.我們將證明，對于每個與互質(zhì)的整數(shù)，都有整除.</p><p>　　定理2.14 設(shè)是一個正整數(shù)，是一個與互質(zhì)的整數(shù).如果是模的階，那么當(dāng)且僅當(dāng)有.特別地，當(dāng)且僅當(dāng)整除，才有，所以整除.</p><p>　　證明：由于關(guān)于模的階為，即.如果，那么，所以</p><p><b>　　.</b></p

42、><p>　　相反的，假設(shè).由除法性質(zhì)得，必存在整數(shù)和使得</p><p><b>　　及.</b></p><p><b>　　那么</b></p><p>　　由于，我們用來整除這個同余類，從而得到</p><p>　　由于，是模的階，那么</p><p&

43、gt;　　假設(shè)，則整除，尤其整除，根據(jù)歐拉定理可得</p><p>　　例如，,由于，我們由歐拉定理知</p><p>　　而且，關(guān)于的階是的一個約數(shù).我們這樣計算階：</p><p><b>　　所以的階是.</b></p><p>　　我們將給出歐拉定理的另一種證明及它的推論.我們將從關(guān)于群的一些簡單觀察開始.我們把

44、群的階定義為群的基數(shù)</p><p>　　定理2.15（拉格朗日定理）假設(shè)是一個有限群，是的子群，則的階整除的階</p><p>　　證明：設(shè)是一個群，運算為乘法，是的一個非空子集.對于任意G,我們定義這個集合：</p><p>　　由定義的映射是一個雙射，所以對于所有的，.假設(shè)是的子群，那么被稱作的一個陪集.設(shè)和是子群的陪集.，則存在，使得，或者，由于是一個子群，

45、，這里.對于所有的，，所以；同理，,所以因此子群的陪集不交或相等.由于的每個元素屬于的陪集（例如，對于所有的都有），從而可得出劃分G的陪集.我們用表示陪集.假設(shè)是一個有限集，則，是有限的，及</p><p><b>　　特別地，我們有整除</b></p><p>　　設(shè)是一個群，運算為乘法.設(shè)，=Z，則.由于對所有的，Z,，從而可得出是的子群.這個子群被稱作由生成的循

46、環(huán)子群，記作，循環(huán)子群都是交換的.</p><p>　　如果存在一個元素，使得，則群是循環(huán)群.此時，元素稱作的生成元.例如，群(Z/7Z是由Z生成的階為6的循環(huán)群.同余類Z是這個群的另一個生成元.如果對于所有整數(shù)，都有，則由生成的這個循環(huán)群是無限的.如果存在和，使得，，則.設(shè)是最小的正數(shù)，且使得，則這個群的元素，，，…，是不同的.設(shè)，由除法知，存在整數(shù)和，使得， .由于</p><p>&

47、lt;b>　　，</b></p><p><b>　　從而有</b></p><p><b>　　Z，</b></p><p>　　由生成的這個循環(huán)群的階為，而且，當(dāng)且僅當(dāng)，才有.</p><p>　　設(shè)是一個群，.我們可以將的階定義為由生成的循環(huán)子群的基數(shù).</p>

48、<p>　　定理2.16 設(shè)是一有限群，，則元素的階整除群的階.</p><p>　　證明：由定理2.15立即可得知，因為的階是由生成的循環(huán)子群的階.</p><p>　　我們可以應(yīng)用到一種特殊情形：當(dāng)是模的剩余類環(huán)中的，則是階為的有限群.設(shè)，是中的階，則也是由生成的循環(huán)子群的階.根據(jù)定理2.16知，整除，及</p><p><b>　　ZZ

49、ZZ</b></p><p><b>　　同樣地，</b></p><p><b>　　，</b></p><p><b>　　這就是歐拉定理.</b></p><p>　　定理2.17 設(shè)是階為的一個循環(huán)群，是的子群.如果是的生成元，則存在唯一的的約數(shù)，使得是由生

50、成的循環(huán)子群，其中的階為.</p><p>　　證明：設(shè)是所有整數(shù)的集合，使得，如果，，則，.由于是一個子群，則，，因此，，是的一個子群.由定理1.3知，存在唯一的非負(fù)整數(shù)，使得Z，所以是由生成的一個循環(huán)子群.由于，我們可得，是的正約數(shù)，的階為.</p><p>　　定理2.18 設(shè)是階為的循環(huán)群，是的一個生成元，對于每個整數(shù)，由生成的循環(huán)子群的階為，則，.特別地，恰好有個生成元.<

51、;/p><p>　　證明：由于，則存在整數(shù)，，使得.則</p><p><b>　　，</b></p><p>　　所以，.由于整除，則存在一個整數(shù)，使得.那么</p><p><b>　　，</b></p><p>　　所以，，.因此，，的階為.特別地，當(dāng)且僅當(dāng)，，所以恰好有個