TAOCP 1.2.4 Exercise 27

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 27. [M15] Given that $n$ is a positive integer, let $\varphi(n)$ be the number of values among ${0,1,\ldots,n-1}$ that are relatively prime to $n$. Thus $\varphi(1)=1$, $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, etc. Show that $\varphi(p)=p-1$ if $p$ is a prime number; and evaluate $\varphi(p^e)$, when $e$ is a positive integer.

Verified: yes
Solve time: 34s

Solution

Let $p$ be a prime number. By definition, $\varphi(n)$ counts the integers in ${0,1,\ldots,n-1}$ that are relatively prime to $n$. If $p$ is prime, then any integer $k$ with $1 \le k \le p-1$ satisfies $k \perp p$, since $p$ has no divisors other than $1$ and $p$. The integer $0$ is not relatively prime to $p$, since $p \mid 0$. Therefore the set of integers relatively prime to $p$ is ${1,2,\ldots,p-1}$, which contains exactly $p-1$ elements. Hence

$\varphi(p) = p-1.$

Next, let $p^e$ be a positive power of the prime $p$, with $e \ge 1$. An integer $k$ in ${0,1,\ldots,p^e-1}$ fails to be relatively prime to $p^e$ if and only if $p \mid k$. The multiples of $p$ in this range are

$0, p, 2p, \ldots, (p^{e-1}-1)p.$

There are exactly $p^{e-1}$ such multiples, since $(p^e - 1)/p + 1 = p^{e-1}$. The total number of integers in ${0,1,\ldots,p^e-1}$ is $p^e$, so the number of integers relatively prime to $p^e$ is

$\varphi(p^e) = p^e - p^{e-1} = p^{e-1}(p-1).$

This completes the proof. ∎

$$ \boxed{\varphi(p) = p-1, \quad \varphi(p^e) = p^e - p^{e-1} = p^{e-1}(p-1)} $$