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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Theorem[edit | edit source]

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 | edit source]

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.