Sum of Euler Phi Function over Divisors
This article has been identified as a candidate for Featured Proof status. If you do not believe that this proof is worthy of being a Featured Proof, please state your reasons on the talk page. To discuss this page in more detail, feel free to use the talk page. |
Theorem
Let $n \in \Z_{>0}$ be a strictly positive integer.
Then $\ds \sum_{d \mathop \divides n} \map \phi d = n$
where:
- $\ds \sum_{d \mathop \divides n}$ denotes the sum over all of the divisors of $n$
- $\map \phi d$ is the Euler $\phi$ function, the number of integers less than $d$ that are prime to $d$.
That is, the total of all the totients of all divisors of a number equals that number.
Proof
Let us define:
- $S_d = \set {m \in \Z: 1 \le m \le n, \gcd \set {m, n} = d}$.
That is, $S_d$ is all the numbers less than or equal to $n$ whose GCD with $n$ is $d$.
Now from Integers Divided by GCD are Coprime we have:
- $\gcd \set {m, n} = d \iff \dfrac m d, \dfrac n d \in \Z: \dfrac m d \perp \dfrac n d$
So the number of integers in $S_d$ equals the number of positive integers no bigger than $\dfrac n d$ which are prime to $\dfrac n d$.
That is, by definition of the Euler phi function:
- $\card {S_d} = \map \phi {\dfrac n d}$
From the definition of the $S_d$, it follows that for all $1 \le m \le n$:
- $\exists d \divides n: m \in S_d$
Therefore:
- $\ds \set {1, \ldots, n} = \bigcup_{d \mathop \divides n} S_d$
Moreover, it follows from the definition of the $S_d$ that they are pairwise disjoint.
Now from Corollary to Cardinality of Set Union, it follows that:
\(\ds n\) | \(=\) | \(\ds \sum_{d \mathop \divides n} \card {S_d}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{d \mathop \divides n} \map \phi {\dfrac n d}\) |
But from Sum Over Divisors Equals Sum Over Quotients:
- $\ds \sum_{d \mathop \divides n} \map \phi {\dfrac n d} = \sum_{d \mathop \divides n} \map \phi d$
and hence the result.
$\blacksquare$
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 25 \alpha$
- 1976: Tom M. Apostol: Introduction to Analytic Number Theory ... (previous) ... (next): $2.3$: The Euler totient function $\map \varphi n$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences: Exercise $16$