Abstract Algebra/Group Theory/Subgroup/Cyclic Subgroup/Euler's Totient Theorem

Theorem edit

Let n be a positive integer. Let x be an integer relatively prime to n Let φ(n) = number of positive integers less than and relatively prime to n

 

Proof edit

  with multiplication mod n is a Group of positive integers less than and relatively prime to integer n.

φ(n) = o( )

Let X be the cyclic subgroup of   generated by x mod n.

As X is subgroup of  

0. o(X) divides o( )
1. o( ) / o(X) is an integer
2.