Section9.2The Euler Phi Function

We give the size of the group of units mod (\(n\)) a special name.

Definition9.2.1
We give the order of \(U_n\) the name \(\phi(n)\). That is, by definition, \[\phi(n)=|U_n |\; .\]

This is the so-called Euler \(\phi\) function. It can also be written phi, it is pronounced 'fee', and it's occasionally notated \(\varphi\) just for fun.

One of the most fun things to do with basic number theory is to explore new concepts with pencil and paper - because it really is tractable. Do you see any patterns on the value of \(\phi(n)\)?

Subsection9.2.1Euler's Theorem

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)\]
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. In particular, we have proved one of the many celebrated theorems of Leonhard Euler:

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?