Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Divisors, Tau

The definition and key theorems involving Euler's Totient function.  For more info, see the "related pages" listed below.

Definition

τ(n) is the number of positive divisors of n

Calculating τ(n)

Let x = p1e1 p2e2 ... pnen 

The factors of x are all the numbers of the form

y = p1d1 p2d2 ... pndn,

where the di each independently range from 0 to ei.  There are (1+ei) ways to choose the exponent of the i'th prime factor, so

τ(x) = (1+e1) (1+e2)...(1+en)

A surprising identity: sum(k=1 to n) tau(k) = sum(h=1 to n) [n/h]

 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.

Related pages in this website

φ(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.