So far this is a relatively abstract concept. What follows is not abstract at all, but very, very useful! Let's follow the following argument to see what we can find out about \(\phi(n)\).

Recall the notion of the order of an element (Definition 8.3.9). So any random element \([a]\in U_n\) (for some \(n\)) has an order. For instance, the order of \([2]\) in \(U_7\) is 3, because \([2]^1\) and \([2]^2\) are not \(1\), but \([2]^3\equiv 8\equiv 1\) (mod \(7\)).

This means we can apply the things we learned about orders, in particular Theorem 8.3.11 of Lagrange. It stated that the order of any element of a finite group divides the order of the group itself.

Think about what this implies for orders in \(|U_n|\). First, \(|a|\) divides \(|U_n|\). (For instance, in the example above, 3 divides 6.) That can be rewritten as \begin{equation*}|a|\; \mid \; \phi(n)\text{, or }\phi(n)=k|a|\end{equation*} for some positive integer \(k\).

Finally, let's apply this fact to powers of \(a\). \begin{equation*}a^{\phi(n)}=a^{k|a|}=(a^{|a|})^k\equiv 1^k\equiv 1\text{ (mod }n)\end{equation*} This is very interesting; without it, all we would know is that \(a^{|a|}\equiv 1\) because that's the definition of what ‘order’ means. With it, we have proved one of the many celebrated theorems of Leonhard Euler:

Try verifying Euler's Theorem for \(n=12\) and \(n=11\) for some simple \(a\) such as \(a=3\) or \(a=5\). Can you see how to recover Fermat's Little Theorem from Euler's Theorem, as a special case? (See Exercise 9.6.1.)