Sum of Euler Phi Function over Divisors

From ProofWiki
Jump to navigation Jump to search


Let $n \in \Z_{>0}$ be a strictly positive integer.

Then $\displaystyle \sum_{d \mathop \divides n} \map \phi d = n$


$\displaystyle \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.


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$


$\displaystyle \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:

\(\displaystyle n\) \(=\) \(\displaystyle \sum_{d \mathop \divides n} \card {S_d}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{d \mathop \divides n} \map \phi {\dfrac n d}\)

But from Sum Over Divisors Equals Sum Over Quotients:

$\displaystyle \sum_{d \mathop \divides n} \map \phi {\dfrac n d} = \sum_{d \mathop \divides n} \map \phi d$

and hence the result.