Difference between revisions of "Divisor function"
| Line 1: | Line 1: | ||
| − | The '''divisor function''' is denoted <math>\sigma_k(n)</math> and is defined as the sum of the <math>k</math>th [[power]]s of the [[divisor]]s of <math>n</math>. Thus <math>\sigma_k(n) = \sum_{d|n}d^k = d_1 + d_2 + \cdots + d_r</math> where the <math>d_i</math> are the divisors of <math>n</math>. | + | The '''divisor function''' is denoted <math>\sigma_k(n)</math> and is defined as the sum of the <math>k</math>th [[power]]s of the [[divisor]]s of <math>n</math>. Thus <math>\sigma_k(n) = \sum_{d|n}d^k = d_1^k + d_2^k + \cdots + d_r^k</math> where the <math>d_i</math> are the divisors of <math>n</math>. |
== Counting divisors == | == Counting divisors == | ||
| − | + | Note that $\sigma_0(n) = d_1^0 + d_2^0 + \ldots + d_r^0 = 1 + 1 + \ldots + 1 = r</math>, the number of divisors of $n$. Thus <math>\sigma_0(n) = d(n)</math> is simply the number of divisors of <math>n</math>. | |
=== Example === | === Example === | ||
Revision as of 09:49, 29 July 2006
The divisor function is denoted 
and is defined as the sum of the 
th powers of the divisors of 
. Thus 
where the 
are the divisors of .
Counting divisors
Note that $\sigma_0(n) = d_1^0 + d_2^0 + \ldots + d_r^0 = 1 + 1 + \ldots + 1 = r</math>, the number of divisors of $n$. Thus 
is simply the number of divisors of .
Example
Consider the task of counting the divisors of 72.
- First, we find the prime factorization of 72:
- Since each divisor of 72 can have a power of 2, and since this power can be 0, 1, 2, or 3, we have 4 possibilities. Likewise, since each divisor can have a power of 3, and since this power can be 0, 1, or 2, we have 3 possibilities. By an elementary counting principle, we have
divisors.
divisors.We can now generalize. Let the prime factorization of be 
. Any divisor of must be of the form 
where the 
are integers such that 
for 
. Thus, the number of divisors of is 
.
Sum of divisors
The sum of the divisors, or 
, is given by
