Skip to main content

Section 9.2 The Euler Phi Function

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

Definition 9.2.1.

We give the order of \(U_n\) the name \(\phi(n)\text{.}\) That is, by definition,

\begin{equation*} \phi(n)=|U_n |\text{.} \end{equation*}

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. We'll meet Euler many times in this text; see Historical remark 13.0.3.

Remark 9.2.2.

Since modulo one everything is one, we say \(U_1=\{[1]\}\) and \(\phi(1)=1\) since \(\gcd(1,1)=1\text{,}\) despite the fact that also everything is zero. If this bothers you, you are nearly at the algebraic notion of a field mentioned toward the end of Section 8.1, and may wish to read some discussions of the field with one element.

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.

Question 9.2.3.

Do you see any patterns on the value of \(\phi(n)\text{?}\)

Subsection 9.2.1 Euler's theorem

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)\text{.}\)

Recall the notion of the order of an element (Definition 8.3.10). So any random element \([a]\in U_n\) (for some \(n\)) has an order.

Example 9.2.4.

For instance, the order of \([2]\) in \(U_7\) is 3, because \([2]^1\) and \([2]^2\) are not \(1\text{,}\) 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.12 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|\text{.}\) First, \(|a|\) divides \(|U_n|\text{.}\) (For instance, in Example 9.2.4, 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\text{.}\)

Finally, let's apply this fact to powers of \(a\text{.}\)

\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:

See the preceding paragraphs.

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