tceic.com

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

Euler’s Theorem and Fermat’s Theorem Book: Elementary Methods in number theory Author :Melvyn B. Nathanson Page: P67 ? P71 2.5 Euler’s Theorem and Fermat’s Theorem Euler’s theorem and its corollary ,Fermat’s 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 cryptography. Theorem2.12（Euler）Let m be a positive integer, and let a be an integer relatively prime to m .Then a? ?m? ? 1?modm? . Proof. Let r1 ,?r? ?m ? be a reduced set of residues modulo m .Since ? ? ?a, m? ? 1 ，we have ?ari , m? ? 1?i ? 1,?? ?m?? exists for i ? 1,?, ? (m) .Consequently, for every i ? ? 1,?? ?m?? there ? ?i ? ? ? 1,?? ?m??such that ari ? r? ?i ? ?modm?. Moreover， ari ? arj ?modm? if and only if set ? 1,?? ?m?? and ar 1 ,?ar ? ?m ? that i ? j ，and so ? is a permutation of the ? ? is also a reduced set of residues modulo ? ?ar1 ??ar2 ?? ?ar? ?m ? ??modm ? m .It follows a ? ? m ?r1r2 ?r? ? m ? ? r? ?1?r? ?2? ?r? ?m? ?m o d m? ? r1r2 ?r? ?m? ?modm? Dividing by r1r2 ?r? ?m ? ，we obtain a? ?m? ? 1?modm? This completes the proof. The following corollary is sometimes called Fermat’s litter theorem. Theorem 2.13 (Fermat) Let p be a prime number .If the integer a is not divisible by p ,then a r ?1 ? 1?mod p ? Moreover, a p ? a?mod p? for every integer a . Proof. If