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^{φ (n)} \equiv 1 (\mod n)

Proof

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

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

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

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

0. o(X) divides o(

ℤ / n^{\times}

)

1. o(

ℤ / n^{\times}

) / o(X) is an integer

2.

x^{φ (n)} = x^{o (ℤ / n^{\times})} = x^{o (X) o (ℤ / n^{\times}) / o (X)} = [x^{o (X)}]^{o (ℤ / n^{\times}) / o (X)} = e^{o (ℤ / n^{\times}) / o (X)} = e