Divisors, Tau

Math Help -> Number Theory -> Theorems -> Divisors, Tau function

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₁^e1 p₂^e2 ... p_n^en

The factors of x are all the numbers of the form

y = p₁^d1 p₂^d2 ... p_n^dn,

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+e₂)...(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 the Math Help site is Graeme McRae.
[home] [email] [search] [Links to Math Sites] [Whiteboard]