
The definition and key theorems involving Euler's Totient function. For more info, see the "related pages" listed below.
τ(n) is the number of positive divisors of n
Let x = p_{1}^{e}1 p_{2}^{e}2 ... p_{n}^{e}n
The factors of x are all the numbers of the form
y = p_{1}^{d}1 p_{2}^{d}2 ... p_{n}^{d}n,
where the d_{i} each independently range from 0 to e_{i}. There are (1+e_{i}) ways to choose the exponent of the i'th prime factor, so
τ(x) = (1+e_{1}) (1+e_{2})...(1+e_{n})
n
Σ
k=1τ(k) = n
Σ
h=1[n/h]
This is most easily proved by induction on n. It's true when n=1, because τ(1) = 1, and [1/1] = 1.
[(n+1)/h]  [n/h] = 1 or 0, depending on whether h is a divisor of n+1 or not. Therefore,
n+1
Σ
h=1[(n+1)/h] − n+1
Σ
h=1[n/h] = τ(n+1)
And since [n/(n+1)]=0,
n+1
Σ
h=1[(n+1)/h] − n
Σ
h=1[n/h] = τ(n+1),
which establishes the truth of the identity for n+1.
φ(n), the number of coprimes to n: Totient function
μ(n), the M�bius function
The webmaster and author of this Math Help site is Graeme McRae.