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

Theorem

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

$x^{\varphi (n)}\equiv 1{\pmod {n}}$

Proof

$\mathbb {Z} /n^{\times }$ with multiplication mod n is a Group of positive integers less than and relatively prime to integer n.

φ(n) = o($\mathbb {Z} /n^{\times }$)

Let X be the cyclic subgroup of $\mathbb {Z} /n^{\times }$ generated by x mod n.

As X is subgroup of $\mathbb {Z} /n^{\times }$

0. o(X) divides o($\mathbb {Z} /n^{\times }$)

1. o($\mathbb {Z} /n^{\times }$) / o(X) is an integer

2. $x^{\varphi (n)}=x^{o(\mathbb {Z} /n^{\times })}=x^{o(X)o(\mathbb {Z} /n^{\times })/o(X)}=[x^{o(X)}]^{o(\mathbb {Z} /n^{\times })/o(X)}=e^{o(\mathbb {Z} /n^{\times })/o(X)}=e$