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