euler'stheorem

Euler's Theorem

a**(phi(n))==1 [mod n][hcf (a,n)=1]

Proof:

Let a1, a2, a3, …, a(phi(n)) be the integers less than n which are coprime with n

Then aa1, aa2, aa3, …, aa(phi(n)) are congruent (not necessarily in the same order) to a1, a2, a3, …, a(phi(n)) [mod n][Lemma 1]

=> aa1aa2aa3…aa(phi(n))==a1a2a3…a(phi(n)) [mod n]

Since hcf (a1a2a3…a(phi(n)),n)=1, can divide both sides of congruence above by a1a2a3…a(phi(n)), to give result

LEMMA 1

Let n>1 and hcf (a,n)=1. a1,a2,a3,…,a(phi(n)) are congruent, in some order, to aa1,aa2,aa3,…,aa(phi(n)) [mod n]

Proof:

aai==aaj [mod n] => ai==aj [mod n], which is false

So, no two of aa1,aa2,aa3,…,aa(phi(n)) are congruent [mod n]

Also, hcf (ai,n)=1 and hcf (a,n)=1 => hcf (aai,n) =1

so, if aai==b [mod n], then b is one of the integers a1,a2,a3,…,a(phi(n))