# Theorem

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

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

# Proof

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

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

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

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

0. o(X) divides o(${\displaystyle \mathbb {Z} /n^{\times }}$)
1. o(${\displaystyle \mathbb {Z} /n^{\times }}$) / o(X) is an integer
2. ${\displaystyle 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}$