Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Divisor function"
 
(5 intermediate revisions by 3 users not shown)
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 [[positive]] divisors of <math>n</math>.
  
 
== Counting divisors ==
 
== 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>.
+
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.
  
−
: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>72=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>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_k + p_k^2 + \cdots + p_k^{e_k}).</math> </center>
 +
 
 +
There will be <math>(e_1+1)(e_2+1)(e_3+1)\cdots (e_k+1)</math> products formed by taking one number from each sum, which is the number of divisors of <math>n</math>.  Clearly all possible products are divisors of <math>n</math>.  Furthermore, all of those products are unique since each positive integer has a unique prime factorization. 
 +
 
 +
Since all of these products are added together, we can conclude this gives us the sum of the divisors.
 +
 
 +
== Sum of kth Powers of Divisors ==
 +
 
 +
Inspired by the example of the sum of divisors, we can easily see that the sum of the <math>k^\text{th}</math> powers of the divisors is given by
 +
<cmath>\begin{align*}
 +
\sigma_k(n) &= (1+p_1^k+p_1^{2k}+\cdots +p_1^{e_1k})(1+p_2^k+p_2^{2k}+\cdots +p_2^{e_2k})\cdots (1+p_i^k+p_i^{2k}+\cdots +p_i^{e_ik}) \\
 +
&= \prod_{a=1}^{i}\left(\sum_{b=0}^{e_a}p_a^{bk}\right)
 +
\end{align*}</cmath>
 +
where <math>p_1,p_2,...,p_i</math> are the distinct prime divisors of <math>n</math>.
 +
 
 +
This is proven in a very similar way to the <math>\sigma_1</math> case.
  
 
== See also ==
 
== See also ==
 
* [[Divisibility]]
 
* [[Divisibility]]
 
* [[Number theory]]
 
* [[Number theory]]
 +
 +
{{stub}}

Latest revision as of 05:58, 21 May 2009

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^k + d_2^k + \cdots + d_r^k$ where the $d_i$ are the positive divisors of $n$.

Counting divisors

Note that $\sigma_0(n) = d_1^0 + d_2^0 + \ldots + d_r^0 = 1 + 1 + \ldots + 1 = r$, the number of divisors of $n$. Thus $\sigma_0(n) = d(n)$ is simply the number of divisors of $n$.

Example Problems

Demonstration

Consider the task of counting the divisors of 72.

First, we find the prime factorization of 72: $72=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 $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)$.


Introductory Problems


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_k + p_k^2 + \cdots + p_k^{e_k}).$

There will be $(e_1+1)(e_2+1)(e_3+1)\cdots (e_k+1)$ products formed by taking one number from each sum, which is the number of divisors of $n$. Clearly all possible products are divisors of $n$. Furthermore, all of those products are unique since each positive integer has a unique prime factorization.

Since all of these products are added together, we can conclude this gives us the sum of the divisors.

Sum of kth Powers of Divisors

Inspired by the example of the sum of divisors, we can easily see that the sum of the $k^\text{th}$ powers of the divisors is given by \begin{align*} \sigma_k(n) &= (1+p_1^k+p_1^{2k}+\cdots +p_1^{e_1k})(1+p_2^k+p_2^{2k}+\cdots +p_2^{e_2k})\cdots (1+p_i^k+p_i^{2k}+\cdots +p_i^{e_ik}) \\ &= \prod_{a=1}^{i}\left(\sum_{b=0}^{e_a}p_a^{bk}\right) \end{align*} where $p_1,p_2,...,p_i$ are the distinct prime divisors of $n$.

This is proven in a very similar way to the $\sigma_1$ case.

See also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisor_function&oldid=31790"