Editing Divisor function (section)

==Properties==

===Formulas at prime powers===

For a [[prime number]] ''p'',

:<math>\begin{align}
\sigma_0(p) & = 2 \\
\sigma_0(p^n) & = n+1 \\
\sigma_1(p) & = p+1
\end{align}</math>

because by definition, the factors of a prime number are 1 and itself. Also, where ''p<sub>n</sub>''# denotes the [[primorial]],

:<math> \sigma_0(p_n\#) = 2^n </math>

since ''n'' prime factors allow a sequence of binary selection (<math>p_{i}</math> or 1) from ''n'' terms for each proper divisor formed. However, these are not in general the smallest numbers whose number of divisors is a [[power of two]]; instead, the smallest such number may be obtained by multiplying together the first ''n'' [[Fermi–Dirac prime]]s, prime powers whose exponent is a power of two.<ref>{{citation
 | last = Ramanujan | first = S. | author-link = Srinivasa Ramanujan
 | doi = 10.1112/plms/s2_14.1.347
 | issue = 1
 | journal = Proceedings of the London Mathematical Society
 | pages = 347–409
 | title = Highly Composite Numbers
 | volume = s2-14
 | year = 1915| url = https://zenodo.org/record/1433496 }}; see section 47, pp. 405–406, reproduced in ''Collected Papers of Srinivasa Ramanujan'', Cambridge Univ. Press, 2015, [https://books.google.com/books?id=h1G2CgAAQBAJ&pg=PA124 pp. 124–125]</ref>

Clearly, <math>1 < \sigma_0(n) < n</math> for all <math>n > 2</math>, and <math>\sigma_x(n) > n </math> for all <math>n > 1</math>, <math>x > 0</math> .

The divisor function is [[multiplicative function|multiplicative]] (since each divisor ''c'' of the product ''mn'' with <math>\gcd(m, n) = 1</math> distinctively correspond to a divisor ''a'' of ''m'' and a divisor ''b'' of ''n''), but not [[Completely multiplicative function|completely multiplicative]]:

:<math>\gcd(a, b)=1 \Longrightarrow \sigma_x(ab)=\sigma_x(a)\sigma_x(b).</math>

The consequence of this is that, if we write

:<math>n = \prod_{i=1}^r p_i^{a_i}</math>

where ''r''&nbsp;=&nbsp;''ω''(''n'') is the [[prime omega function|number of distinct prime factors]] of ''n'', ''p<sub>i</sub>'' is the ''i''th prime factor, and ''a<sub>i</sub>'' is the maximum power of ''p<sub>i</sub>'' by which ''n'' is [[divisible]], then we have: {{sfnp|Hardy|Wright|2008|pp=310 f|loc=§16.7}}

:<math>\sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = \prod_{i=1}^r \left (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x} \right ).</math>

which, when ''x''&nbsp;&ne;&nbsp;0, is equivalent to the useful formula: {{sfnp|Hardy|Wright|2008|pp=310 f|loc=§16.7}}

:<math>\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}.</math>

When ''x''&nbsp;=&nbsp;0, <math>\sigma_0(n)</math> is: {{sfnp|Hardy|Wright|2008|pp=310 f|loc=§16.7}}

:<math>\sigma_0(n)=\prod_{i=1}^r (a_i+1).</math>

This result can be directly deduced from the fact that all divisors of <math>n</math> are uniquely determined by the distinct tuples <math>(x_1, x_2, ..., x_i, ...,  x_r)</math> of integers with <math>0 \le x_i \le a_i</math> (i.e. <math>a_i+1</math> independent choices for each <math>x_i</math>).

For example, if ''n'' is 24, there are two prime factors (''p''<sub>1</sub> is 2; ''p''<sub>2</sub> is 3); noting that 24 is the product of 2<sup>3</sup>×3<sup>1</sup>, ''a''<sub>1</sub> is 3 and ''a''<sub>2</sub> is 1. Thus we can calculate <math>\sigma_0(24)</math> as so:

: <math>\sigma_0(24) = \prod_{i=1}^{2} (a_i+1) = (3 + 1)(1 + 1) = 4 \cdot 2 = 8.</math>

The eight divisors counted by this formula are 1, 2, 4, 8, 3, 6, 12, and 24.

===Other properties and identities===
[[Euler]] proved the remarkable recurrence:<ref>{{Cite arXiv |eprint = math/0411587|last1 = Euler|first1 = Leonhard|title = An observation on the sums of divisors|last2 = Bell|first2 = Jordan|year = 2004}}</ref><ref>https://scholarlycommons.pacific.edu/euler-works/175/, ''Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs''</ref><ref>https://scholarlycommons.pacific.edu/euler-works/542/, ''De mirabilis proprietatibus numerorum pentagonalium''</ref>

:<math>\begin{align}
\sigma_1(n) &= \sigma_1(n-1)+\sigma_1(n-2)-\sigma_1(n-5)-\sigma_1(n-7)+\sigma_1(n-12)+\sigma_1(n-15)+ \cdots \\[12mu]
 &= \sum_{i\in\N} (-1)^{i+1}\left( \sigma_1 \left( n-\frac{1}{2} \left( 3i^2-i \right) \right) + \sigma_1 \left( n-\frac{1}{2} \left( 3i^2+i \right) \right) \right),
\end{align}</math>

where <math>\sigma_1(0)=n</math> if it occurs and <math>\sigma_1(x)=0</math> for <math>x < 0</math>, and <math>\tfrac{1}{2} \left( 3i^2 \mp i \right)</math> are consecutive pairs of generalized [[pentagonal numbers]] ({{OEIS2C|A001318}}, starting at offset 1). Indeed, Euler proved this by logarithmic differentiation of the identity in his [[pentagonal number theorem]].

For a non-square integer, ''n'', every divisor, ''d'', of ''n'' is paired with divisor ''n''/''d'' of ''n'' and <math>\sigma_{0}(n)</math> is even; for a square integer, one divisor (namely <math>\sqrt n</math>) is not paired with a distinct divisor and <math>\sigma_{0}(n)</math> is odd. Similarly, the number <math>\sigma_{1}(n)</math> is odd if and only if ''n'' is a square or twice a square.{{sfnp|Gioia|Vaidya|1967}}

We also note ''s''(''n'') = ''σ''(''n'')&nbsp;−&nbsp;''n''. Here ''s''(''n'') denotes the sum of the ''proper'' divisors of ''n'', that is, the divisors of ''n'' excluding ''n'' itself. This function is used to recognize [[perfect number]]s, which are the ''n'' such that ''s''(''n'') =&nbsp;''n''. If ''s''(''n'') > ''n'', then ''n'' is an [[abundant number]], and if ''s''(''n'') < ''n'', then ''n'' is a [[deficient number]].

If {{mvar|n}} is a power of 2, <math>n = 2^k</math>, then <math>\sigma(n) = 2 \cdot 2^k - 1 = 2n - 1</math> and <math>s(n) = n - 1</math>, which makes ''n'' [[Almost perfect number|almost-perfect]].

As an example, for two primes <math>p,q:p<q</math>, let

:<math>n = p\,q</math>.

Then

:<math>\sigma(n)  = (p+1)(q+1) = n + 1 + (p+q), </math>
:<math>\varphi(n) = (p-1)(q-1) = n + 1 - (p+q), </math>

and

:<math>n + 1 = (\sigma(n) + \varphi(n))/2, </math>
:<math>p + q = (\sigma(n) - \varphi(n))/2, </math>

where <math>\varphi(n)</math> is [[Euler phi|Euler's totient function]].

Then, the roots of

:<math>(x-p)(x-q) = x^2 - (p+q)x + n = x^2 - [(\sigma(n) - \varphi(n))/2]x + [(\sigma(n) + \varphi(n))/2 - 1] = 0 </math>

express ''p'' and ''q'' in terms of ''σ''(''n'') and ''φ''(''n'') only, requiring no knowledge of ''n'' or <math>p+q</math>, as

:<math>p = (\sigma(n) - \varphi(n))/4 - \sqrt{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}, </math>
:<math>q = (\sigma(n) - \varphi(n))/4 + \sqrt{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}. </math>

Also, knowing {{mvar|n}} and either <math>\sigma(n)</math> or <math>\varphi(n)</math>, or, alternatively, <math>p+q</math> and either <math>\sigma(n)</math> or <math>\varphi(n)</math> allows an easy recovery of ''p'' and ''q''.

In 1984, [[Roger Heath-Brown]] proved that the equality

:<math>\sigma_0(n) = \sigma_0(n + 1)</math>

is true for infinitely many values of {{mvar|n}}, see {{OEIS2C|A005237}}.

=== Dirichlet convolutions ===
{{Main article|Dirichlet convolution}}
By definition:<math display="block">\sigma = \operatorname{Id} * \mathbf 1</math>By [[Möbius inversion formula|Möbius inversion]]:<math display="block">\operatorname{Id} = \sigma * \mu   </math>