Euler Phi Function of Prime Power
From ProofWiki
(Redirected from Euler Phi Function of a Prime)
Contents |
Theorem
Let $p^n$ be a prime power for some prime number $p > 1$.
Then:
- $\phi \left({p^n}\right) = p^n \left({1 - \dfrac 1 p}\right)$
where $\phi: \Z_{>0} \to \Z_{>0}$ is the Euler $\phi$ function.
When $n = 1$ the expression degenerates to:
- $\phi \left({p}\right) = p - 1$
Corollary
When $p = 2$, the formula is exceptionally simple:
- $\phi \left({2^k}\right) = 2^{k-1}$
Proof
From the definition of a prime number, the only number less than or equal to a prime $p$ which is not prime to $p$ is $p$ itself.
Thus it follows directly that: $\phi \left({p}\right) = p - 1$
$\Box$
From Prime Not Divisor then Coprime:
- $k \perp p^n \iff p \nmid k$
There are $p^{n-1}$ numbers $k$ such that $1 \le k \le p^n$ which are divisible by $p$:
- $k \in \left\{{p, 2 p, 3 p, \ldots, \left({p^{n - 1}}\right) p}\right\}$
Therefore:
- $\displaystyle \phi \left({p^n}\right) = p^n - p^{n-1} = p^n \left({1 - \frac 1 p}\right)$
When $n = 1$, note that:
- $\displaystyle \phi \left({p^1}\right) = p^1 \left({1 - \frac 1 p}\right) = p - 1$
demonstrating the compatibility of these definitions.
$\blacksquare$
Sources
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Exercise $27$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 25$