NTIC The Euler Phi Function

🔗

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.

🔗

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:

🔗

Theorem 9.2.5. Euler's Theorem.

If $\gcd(a,n)=1\text{,}$ then $a^{\phi(n)}\equiv 1$ (mod $n$ ).

🔗

Proof.

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.)