Euler’s Theorem and Fermat ’s TheoremBook: Elementary Methods in number theoryAuthor :Melvyn B. NathansonPage :7167P P -2.5 Euler’s Theorem and Fermat ’s TheoremEuler ’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 m o d 21σσσ ≡()()m r r r m mod 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 pTheorem 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 lk 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 dmod 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 andr such thatr 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 mod 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)15(mod 178≡Moreover, the order of 7 with respect to 15 is a divisor of 8. We can compute the order as follows:)15(mod 771≡)15(mod 44972≡≡)15(mod 132873≡≡)15(mod 19174≡≡And so the order of 7 is 4.We shall give a second proof of Euler ’s theorem and its corollaries .we begin with some simple observations about groups. We define the order of a group as the cardinality of the group.Theorem 2.15 (Lagrange ’s theorem) If G is a finite group and H is a subgroup of G , then the order of H divides the order of GProof .Let G be a group ,written multiplicatively, and let X be a nonempty subset of G .For every ∈a G ,we define the set):{X x ax aX ∈=The map aX X f →: defined by ax x f =)( is a bijection, and so aX X = for all ∈a G .If H is subgroup of G , then aH is called a coset of H . Let aH and bH be cosets of the subgroup H 。

If φ≠⋂bH aH ,then there exist H y x ∈,such that by ax =，or ,since H is a subgroup,az axy b ==-1，where H xy z ∈=-1。

Then ah azh bh ∈= forall H h ∈and so aH bH ⊆.By symmetry , aH bH ⊆,and so aH bH =.Therefore , cosets of a subgroup H are either disjoint or equal .Since every element of G belongs to some coset of H （for example , a aH ∈ for all ∈a G ），it follows that the cosets of H partitionG .We denote the set of cosets by G H .If G is a finite group, then H and G H are finite ,andG H G H = In particular, we see that H divides G .Let G be a group ,written multiplicatively ,and let a G ∈.Let {:}k H a k z =∈.Then 01a H G =∈⊆。

Since k l k l a a a += for all ,k l Z ∈，it follows that H is a subgroup of G .This subgroup is called the cyclic subgroup generated by a ,and written a .Cyclic subgroups are abelian.The group G is cyclic if there exists an element G a ∈such that a G =.In this cases ,the element a is called a generator of G 。