Difference between revisions of "Divisor function"
m |
(added intro example problem) |
||
Line 5: | Line 5: | ||
Note that <math>\sigma_0(n) = d_1^0 + d_2^0 + \ldots + d_r^0 = 1 + 1 + \ldots + 1 = r</math>, the number of divisors of <math>n</math>. Thus <math>\sigma_0(n) = d(n)</math> is simply the number of divisors of <math>n</math>. | Note that <math>\sigma_0(n) = d_1^0 + d_2^0 + \ldots + d_r^0 = 1 + 1 + \ldots + 1 = r</math>, the number of divisors of <math>n</math>. Thus <math>\sigma_0(n) = d(n)</math> is simply the number of divisors of <math>n</math>. | ||
− | === Example === | + | === Example Problems === |
+ | ==== Demonstration ==== | ||
Consider the task of counting the divisors of 72. | Consider the task of counting the divisors of 72. | ||
Line 13: | Line 14: | ||
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>\sigma_0(n) = (e_1+1)(e_2+1)\cdots (e_k+1)</math>. | ||
+ | |||
+ | |||
+ | ==== Introductory Problems ==== | ||
+ | * [[2005_AMC_10A_Problems/Problem_15 | 2005 AMC 10A Problem 15]] | ||
+ | |||
== 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]] | * [[Divisibility]] | ||
* [[Number theory]] | * [[Number theory]] |
Revision as of 10:36, 2 August 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 positive divisors of .
Contents
[hide]Counting divisors
Note that , the number of divisors of . Thus is simply the number of divisors of .
Example Problems
Demonstration
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 .
Introductory Problems
Sum of divisors
The sum of the divisors, or , is given by