Difference between revisions of "Divisor function"

Revision as of 08:50, 29 July 2006

The divisor function is denoted $\sigma_k(n)$ and is defined as the sum of the $k$ th powers of the divisors of $n$ . Thus $\sigma_k(n) = \sum_{d|n}d^k = d_1 + d_2 + \cdots + d_r$ where the $d_i$ are the divisors of $n$ .

Counting divisors

Letting $k=0$ makes all of the terms in $d_1 + d_2 + \cdots + d_r$ equal to 1. Thus, The value of $\sigma_0(n)$ is simply the number of divisors of $n$ .

Example

Consider the task of counting the divisors of 72.

First, we find the prime factorization of 72: $\displaystyle72=2^{3} \cdot 3^{2}.$

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 $3\cdot 4=12$ divisors.

We can now generalize. Let the prime factorization of $n$ be $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ . Any divisor of $n$ must be of the form $p_1^{f_1}p_2^{f_2} \cdots p_k^{e_k}$ where the $\displaystyle f_i$ are integers such that $0\le f_i \le e_i$ for $i = 1,2,\ldots, k$ . Thus, the number of divisors of $n$ is $\sigma_0(n) = (e_1+1)(e_2+1)\cdots (e_k+1)$ .

Sum of divisors

The sum of the divisors, or $\sigma_1(n)$ , is given by

$\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}).$

@@ Line 5: / Line 5: @@
 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 ==
+=== Example ===
 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>
+: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.
+: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>\sigma_0(n) = (e_1+1)(e_2+1)\cdots (e_k+1)</math>.
-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 ==

Page

Toolbox

Search

Difference between revisions of "Divisor function"

Revision as of 08:50, 29 July 2006

Contents

Counting divisors

Example

Sum of divisors

See also