毕业设计（论文）
外 文 文 献 翻 译
译文题目：Euler ’s Theorem and Fermat ’s Theorem 学生姓名： 张云
专 业：数学与统计学院
指导教师： 张吉刚
2009年 12月 30日
Euler’s Theorem and Fermat ’s Theorem
Book: Elementary Methods in number theory
Author :Melvyn B. Nathanson
Page :7167P P
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
()()m a m mod 1≡ϕ.
Proof. Let (){}m r r ϕ ,1be a reduced set of residues modulo m .Since ()1,=m a ，we have ()()()m i m ar i ϕ ,11,== for 1,,()i m ϕ= .Consequently, for every (){}m i ϕ ,1∈there exists ()(){}m i ϕσ ,1∈such that
()()m r ar i i mod σ≡.
Moreover ，()m ar ar j i mod ≡ if and only if j i =，and so σ is a permutation of the set (){}m ϕ ,1 and (){}m ar ar ϕ ,1 is also a reduced set of residues modulo m .It follows that
()()()()()()()m ar ar ar a m r r r m m mod 2121ϕϕϕ ≡
()()()()m r r r m mod 21σσσ ≡
()()m r r r m m o d 21ϕ ≡ Dividing by ()m r r r ϕ 21，we obtain
()()m a m mod 1≡ϕ
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
()p a r mod 11≡-
Moreover,
()p a a p mod ≡
for every integer a .
Proof . If p is prime and does not divide a, then ()1,=p a ，()1-=p p ϕ，and
()()p a a p p mod 11≡≡-ϕ
by Euler’s theorem. Multiplying this congruence by a ，we obtain
()p a a 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 Euler ’s theorem,()()m a m mod 1≡ϕ.The order of a with respect to the modulus m is the smallest positive integer d such that ()m a d mod 1≡.Then ()m d ϕ≤≤1.We shall prove that ()a ord m divides ()m ϕ for every integer a relatively prime to p
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 ()m a a l k mod ≡ if and only if ()d l k mod ≡.In particular, ()m a n mod 1≡ if and only if d divides n ,and so d divides ()m ϕ.
Proof. Since a has order modulo m ,we have ()m a d mod 1≡.If ()d l k mod ≡，then dq l k +=，and so
()()m a a a a a l
q d l dq l k mod ≡==+. Conversely, suppose that ()m a a l k mod ≡.By the division algorithm, there exist integers q and r such that
r dq l k +=-and 10-≤≤d r .
Then
()()m a a a a a a a r k r q d
l r dq l k mod ≡==++ Since ()1,=m a k ，we can divide this congruence by k a and obtain
()m a r
m o d 1≡ Since 10-≤≤d r ， and d is the order of a modulo m, it follows that 0=r ,and so ()d l k mod ≡.
If )(mod 1m a a
n ≡≡，then d divides n .In particular, d divides )(m ϕ，since )(mod 1)(m a m ≡ϕ by Euler ’s theorem.
For example; let 15=m and a=7.Since 8)15(=ϕ，Euler ’s theorem tells us that
