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 + d_2 + \cdots + d_r</math> where the <math>d_i</math> are the divisors of <math>n</math>. | ||
| − | == | + | == Counting divisors == |
Letting <math>k=0</math> makes all of the terms in <math>d_1 + d_2 + \cdots + d_r</math> equal to 1. Thus, The value of <math>\sigma_0(n)</math> is simply the number of divisors of <math>n</math>. | Letting <math>k=0</math> makes all of the terms in <math>d_1 + d_2 + \cdots + d_r</math> equal to 1. Thus, The value of <math>\sigma_0(n)</math> is simply the number of divisors of <math>n</math>. | ||
| − | + | == Example: 72 == | |
| + | Consider the task of counting the divisors of 72. | ||
| + | |||
| + | First, we find the [[prime factorization]] of 72: <math>\displaystyle72=2^{3} \cdot 3^{2}.</math> | ||
| + | |||
| + | 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 <math>3\cdot 4=12</math> divisors. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | We can now generalize. Let the prime factorization of <math>n</math> be <math>p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}</math>. Any divisor of <math>n</math> must be of the form <math>p_1^{f_1}p_2^{f_2} \cdots p_k^{e_k}</math> where the <math>\displaystyle f_i </math> are integers such that <math>0\le f_i \le e_i</math> for <math>i = 1,2,\ldots, k</math>. Thus, the number of divisors of <math>n</math> is <math>(e_1+1)(e_2+1)\cdots (e_k+1)</math>. | ||
== Sum of divisors == | == Sum of divisors == | ||
The sum of the divisors, or <math>\sigma_1(n)</math>, is given by <center><math> \sigma_1(n) = (1 + p_1 + p_1^2 +\cdots p_1^{e_1})(1 + p_2 + p_2^2 + \cdots + p_2^{e_2}) \cdots (1 + p_n + p_n^2 + \cdots + p_n^{e_n}).</math> </center> | The sum of the divisors, or <math>\sigma_1(n)</math>, is given by <center><math> \sigma_1(n) = (1 + p_1 + p_1^2 +\cdots p_1^{e_1})(1 + p_2 + p_2^2 + \cdots + p_2^{e_2}) \cdots (1 + p_n + p_n^2 + \cdots + p_n^{e_n}).</math> </center> | ||
| − | |||
| − | |||
== See also == | == See also == | ||
| + | * [[Divisibility]] | ||
* [[Number theory]] | * [[Number theory]] | ||
Revision as of 08:37, 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
Letting 
makes all of the terms in 
equal to 1. Thus, The value of 
is simply the number of divisors of .
Example: 72
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.
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
