Sum of ϕ of divisors

Dependencies:

  1. Euler's Totient Function
  2. GCD partitioning of Zn

Let $\phi$ be Euler's totient function (which means $|\mathbb{Z}_n^*| = \phi(n)$). Then,

\[ n = \sum_{d \mid n} \phi(d) \]

Proof

$\mathbb{Z}_n$ can be partitioned into $\left\{ d \mathbb{Z}_{\frac{n}{d}}^* : d \mid n\right\}$.

Therefore, \[ n = |\mathbb{Z}_n| = \sum_{d \mid n} \left|d \mathbb{Z}_{\frac{n}{d}}^*\right| = \sum_{d \mid n} \phi\left(\frac{n}{d}\right) = \sum_{d \mid n} \phi(d) \]

Dependency for: None

Info:

Transitive dependencies:

  1. Euler's Totient Function
  2. Integer Division Theorem
  3. GCD is the smallest Linear Combination
  4. Common divisor divides GCD
  5. gcd(a1/d, a2/d, ..., an/d) = gcd(a1, a_2, ..., an)/d
  6. GCD partitioning of Zn