Totient of a prime power

Builds on Euler's totient function Prime number

Statement

Let $p$ be a prime number and let $k$ be a positive integer. Then $\varphi(p^k) = p^{k-1} (p - 1) = p^k - p^{k-1}$ , where $\varphi$ is Euler's totient function.

Remarks

The proof: an integer is coprime to $p^k$ if and only if $p$ does not divide it. Among $1, \dots, p^k$ , the multiples of $p$ are $p, 2p, \dots, p^{k-1} \cdot p$ , so there are $p^{k-1}$ of them. For example, $\varphi(8) = 4$ and $\varphi(27) = 18$ . With the multiplicativity of the totient function, this formula gives $\varphi(n)$ from the prime factorization of $n$ .

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Greatest common divisor definition
Prime number definition
Coprime integers definition
Euler's totient function definition
Totient of a prime power statement

Tag	`0AVY8HKBGD`
URI	`m2://0AVY8HKBGD`
Kind	statement, proposition
Writing	W0 stub
MSC	11A25
Status	This copy of the site has no build data. Run `m2 status 0AVY8HKBGD`.
Uses	Euler's totient function, Prime number

Totient of a prime power

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here