000RM.dvi

632 Perfect numbers

Appendix: Three important number theoretic functions

Letnbe a positive integer with prime factorization

n=

∏k

i=1

paii

There are several important numbers associated withn.

1.The number of divisors ofnis

d(n)=

∏k

i=1

(1 +ai).

2.The sum of divisors ofn, including 1 andnitself, is

σ(n)=

∏k

i=1

paii+1

pi− 1

.

3.The number of positive integers<nwhich are relatively prime to

nis given by

φ(n)=n

∏k

i=1

(

1 −

1

pi

)

.

These functions are all multiplicative in the sense that

f(mn)=f(m)f(n) whenever gcd(m, n)=1.