How is $φ(p^k) = p^k - p^{k-1}$ derived?

Q: How is φ(p^k) = p^k − p^{k−1} derived?

To derive $\varphi(p^k)$, we count the integers from 1 to $p^k$ that are coprime to $p^k$. An integer is not coprime to $p^k$ if and only if it shares a prime factor with $p^k$. Since $p$ is the only prime factor of $p^k$, the non-coprime integers are exactly the multiples of $p$. There are $p^{k-1}$ multiples of $p$ in the range $[1, p^k]$. Subtracting these from the total $p^k$ gives the count of coprime integers: $\varphi(p^k) = p^k - p^{k-1}$.

To derive

\varphi(p^k)

, we count the integers from 1 to

p^k

that are coprime to

p^k

. An integer is not coprime to

p^k

if and only if it shares a prime factor with

p^k

. Since

p

is the only prime factor of

p^k

, the non-coprime integers are exactly the multiples of

p

. There are

p^{k-1}

multiples of

p

in the range

[1, p^k]

. Subtracting these from the total

p^k

gives the count of coprime integers:

\varphi(p^k) = p^k - p^{k-1}

Conditions

$p$ is a prime number.
$k$ is a positive integer (implied by context).
The counting range is from 1 to $p^k$ inclusive.

Reasoning, step by step

Consider the integers from 1 to $p^k$ .
Identify the condition for an integer $a$ to NOT be coprime to $p^k$ : $\gcd(a, p^k) > 1$ .
Since $p$ is the only prime factor of $p^k$ , $\gcd(a, p^k) > 1$ if and only if $p$ divides $a$ .
Count the number of multiples of $p$ in the range $[1, p^k]$ . These are $p, 2p, 3p, \ldots, p^{k-1} \cdot p$ .
The number of such multiples is $p^{k-1}$ .
Subtract the count of non-coprime integers from the total count of integers: $p^k - p^{k-1}$ .
Conclude that $\varphi(p^k) = p^k - p^{k-1}$ .

Example

Let $p=2$ and $k=3$ , so $p^k = 8$ . The integers from 1 to 8 are 1, 2, 3, 4, 5, 6, 7, 8. The multiples of 2 are 2, 4, 6, 8 (there are $2^{3-1} = 4$ of them). The integers coprime to 8 are 1, 3, 5, 7. The count is $8 - 4 = 4$ . Using the formula: $\varphi(8) = 2^3 - 2^2 = 8 - 4 = 4$ .

Common misconceptions

Thinking that all even numbers are not coprime to $p^k$ regardless of $p$ (only multiples of the specific prime $p$ are excluded).
Forgetting that the range includes $p^k$ itself, which is a multiple of $p$ and thus not coprime.

Watch the explanation

BilibiliEuler's totient, Quadratic residues｜封无义

1:12 – 1:35Watch this moment ↗

Explore next

Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.

How is φ(pk)=pk−pk−1φ(p^k) = p^k - p^{k-1}φ(pk)=pk−pk−1 derived?