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))