Thread: Euler's theorem

Will anyone please show me a proof of Euler's theorem.

Thank you soo much in advance!

Originally Posted by jenjen

Will anyone please show me a proof of Euler's theorem.

Your last question was number theory related.
I assume you want to show,
a^phi(n) = 1 (mod n)

I have two proofs.
1)The elementary number theory proof.
2)Group theory proof, it is shorter.

Which one will it be?

Oh thanks for your quick reply. I believe it is the group theory proof. Is that the finite abelian group?

thx

Originally Posted by jenjen

Oh thanks for your quick reply. I believe it is the group theory proof. Is that the finite abelian group?

Yes.

It is an excercise for you (unless you want me to prove it) that the set G_n={1<=x<=n |gcd(x,n)=1} for n>1 is a group under multiplication modulo n. (That is the set of all relative prime elements to n less than n is a group). Since it is finite we have a^m = 1 where m is the number of elements in the group. That is m=phi(n) by definition.
Q.E.D.

Now, this group is isomorphic to Z/nZ (you know the classes of integers modulo n) thus, this is true for all integers relatively prime to n.