Now, 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)\).

• Suppose you take some random element \([a]\in U_n\), for some \(n\).
• Like any other element of a group, it 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).
• So all the stuff we learned about groups and their orders applies, and thankfully, it is now written multiplicatively like our theorems.
• In particular, we can apply the group theory theorem of Lagrange. It stated that the order of any element of a finite group divides the order of the group itself.
• So \(|a|\) divides \(|U_n|\). For instance, in the example above, 3 divides 6.
• Rewriting that says \[|a|\; \mid \; \phi(n)\text{, or }\phi(n)=k|a|\] for some positive integer \(k\).
• Finally, let's apply this fact to \(a\). \[a^{\phi(n)}=a^{k|a|}=(a^{|a|})^k\equiv 1^k\equiv 1\text{ mod }(n)\]

Try verifying this 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?