Arithmetic function#Summation functions

An arithmetic function a is

• completely additive if a(mn) = a(m) + a(n) for all natural numbers m and n;
• completely multiplicative if a(1) = 1 and a(mn) = a(m)a(n) for all natural numbers m and n;

Two whole numbers m and n are called coprime if their greatest common divisor is 1, that is, if there is no prime number that divides both of them.

Then an arithmetic function a is

• additive if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;
• multiplicative if a(1) = 1 and a(mn) = a(m)a(n) for all coprime natural numbers m and n.

In this article, $\backslash sum\_p\; f(p)$ and $\backslash prod\_p\; f(p)$ mean that the sum or product is over all prime numbers:

$$\backslash sum\_p\; f(p)\; =\; f(2)\; +\; f(3)\; +\; f(5)\; +\; \backslash cdots$$

and

$$\backslash prod\_p\; f(p)=\; f(2)f(3)f(5)\backslash cdots.$$

Similarly, $\backslash sum\_\{p^k\}\; f(p^k)$ and $\backslash prod\_\{p^k\}\; f(p^k)$ mean that the sum or product is over all prime powers with strictly positive exponent (so {{math|1=k = 0}} is not included):

$$\backslash sum\_\{p^k\}\; f(p^k)\; =\; \backslash sum\_p\backslash sum\_\{k\; >\; 0\}\; f(p^k)\; =\; f(2)\; +\; f(3)\; +\; f(4)\; +f(5)\; +f(7)+f(8)+f(9)+\backslash cdots.$$

The notations $\backslash sum\_\{d\backslash mid\; n\}\; f(d)$ and $\backslash prod\_\{d\backslash mid\; n\}\; f(d)$ mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if {{math|1=n = 12}}, then

$$\backslash prod\_\{d\backslash mid\; 12\}\; f(d)\; =\; f(1)f(2)\; f(3)\; f(4)\; f(6)\; f(12).$$

The notations can be combined: $\backslash sum\_\{p\backslash mid\; n\}\; f(p)$ and $\backslash prod\_\{p\backslash mid\; n\}\; f(p)$ mean that the sum or product is over all prime divisors of n. For example, if n = 18, then

$$\backslash sum\_\{p\backslash mid\; 18\}\; f(p)\; =\; f(2)\; +\; f(3),$$

and similarly $\backslash sum\_\{p^k\backslash mid\; n\}\; f(p^k)$ and $\backslash prod\_\{p^k\backslash mid\; n\}\; f(p^k)$ mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then

$$\backslash prod\_\{p^k\backslash mid\; 24\}\; f(p^k)\; =\; f(2)\; f(3)\; f(4)\; f(8).$$

The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: $n\; =\; p\_1^\{a\_1\}\backslash cdots\; p\_k^\{a\_k\}$ where p₁ < p₂ < ... < p_k are primes and the a_j are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define the p-adic valuation ν_p(n) to be the exponent of the highest power of the prime p that divides n. That is, if p is one of the p_i then ν_p(n) = a_i, otherwise it is zero. Then

$$n\; =\; \backslash prod\_p\; p^\{\backslash nu\_p(n)\}.$$

In terms of the above the prime omega functions ω and Ω are defined by

{{block indent | em = 1.5 | text = ω(n) = k,}}

{{block indent | em = 1.5 | text = Ω(n) = a₁ + a₂ + ... + a_k.}}

To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms of n and the corresponding p_i, a_i, ω, and Ω.

σ_k(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

σ₁(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

Since a positive number to the zero power is one, σ₀(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

$$\backslash sigma\_k(n)\; =\; \backslash prod\_\{i=1\}^\{\backslash omega(n)\}\; \backslash frac\{p\_i^\{(a\_i+1)k\}-1\}\{p\_i^k-1\}=\; \backslash prod\_\{i=1\}^\{\backslash omega(n)\}\; \backslash left(1\; +\; p\_i^k\; +\; p\_i^\{2k\}\; +\; \backslash cdots\; +\; p\_i^\{a\_i\; k\}\backslash right).$$

Setting k = 0 in the second product gives

$$\backslash tau(n)\; =\; d(n)\; =\; (1\; +\; a\_\{1\})(1+a\_\{2\})\backslash cdots(1+a\_\{\backslash omega(n)\}).$$

φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

$$\backslash varphi(n)\; =\; n\; \backslash prod\_\{p\backslash mid\; n\}\; \backslash left(1-\backslash frac\{1\}\{p\}\backslash right)$$

= n \left(\frac{p_1 - 1}{p_1}\right)\left(\frac{p_2 - 1}{p_2}\right) \cdots \left(\frac{p_{\omega(n)} - 1}{p_{\omega(n)}}\right)

.

J_k(n), the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, {{math|1=φ(n) = J₁(n)}}.

$$J\_k(n)\; =\; n^k\; \backslash prod\_\{p\backslash mid\; n\}\; \backslash left(1-\backslash frac\{1\}\{p^k\}\backslash right)$$

= n^k \left(\frac{p^k_1 - 1}{p^k_1}\right)\left(\frac{p^k_2 - 1}{p^k_2}\right) \cdots \left(\frac{p^k_{\omega(n)} - 1}{p^k_{\omega(n)}}\right)

.

μ(n), the Möbius function, is important because of the Möbius inversion formula. See {{slink|#Dirichlet convolution}}, below.

$$\backslash mu(n)=\backslash begin\{cases\}$$

(-1)^{\omega(n)}=(-1)^{\Omega(n)} &\text{if }\; \omega(n) = \Omega(n)\\

0&\text{if }\;\omega(n) \ne \Omega(n).

\end{cases}

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(n), the Ramanujan tau function, is defined by its generating function identity:

$$\backslash sum\_\{n\backslash geq\; 1\}\backslash tau(n)q^n=q\backslash prod\_\{n\backslash geq\; 1\}(1-q^n)^\{24\}.$$

Although it is hard to say exactly what "arithmetical property of n" it "expresses",Hardy, Ramanujan, § 10.2 (τ(n) is (2π)⁻¹² times the nth Fourier coefficient in the q-expansion of the modular discriminant function)Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6 it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σ_k(n) and r_k(n) functions (because these are also coefficients in the expansion of modular forms).

c_q(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity:

$$c\_q(n)\; =\; \backslash sum\_\{\backslash stackrel\{1\backslash le\; a\backslash le\; q\}\{\; \backslash gcd(a,q)=1\}\}\; e^\{2\; \backslash pi\; i\; \backslash tfrac\{a\}\{q\}\; n\}.$$

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

: If q and r are coprime, then $c\_q(n)c\_r(n)=c\_\{qr\}(n).$

The Dedekind psi function, used in the theory of modular functions, is defined by the formula

$$\backslash psi(n)\; =\; n\; \backslash prod\_\{p|n\}\backslash left(1+\backslash frac\{1\}\{p\}\backslash right).$$

λ(n), the Liouville function, is defined by

$$\backslash lambda\; (n)\; =\; (-1)^\{\backslash Omega(n)\}.$$

All Dirichlet characters χ(n) are completely multiplicative. Two characters have special notations:

The principal character (mod n) is denoted by χ₀(a) (or χ₁(a)). It is defined as

$$\backslash chi\_0(a)\; =\; \backslash begin\{cases\}$$

1 & \text{if } \gcd(a,n) = 1, \\

0 & \text{if } \gcd(a,n) \ne 1.

\end{cases}

The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n):

$$\backslash left(\backslash frac\{a\}\{n\}\backslash right)\; =\; \backslash left(\backslash frac\{a\}\{p\_1\}\backslash right)^\{a\_1\}\backslash left(\backslash frac\{a\}\{p\_2\}\backslash right)^\{a\_2\}\backslash cdots\; \backslash left(\backslash frac\{a\}\{p\_\{\backslash omega(n)\}\}\backslash right)^\{a\_\{\backslash omega(n)\}\}.$$

In this formula $(\backslash tfrac\{a\}\{p\})$ is the Legendre symbol, defined for all integers a and all odd primes p by

\left(\frac{a}{p}\right) = \begin{cases}

\;\;\,0 & \text{if } a \equiv 0 \pmod p,

\\+1 & \text{if }a \not\equiv 0\pmod p \text{ and for some integer }x, \;a\equiv x^2\pmod p

\\-1 & \text{if there is no such } x. \end{cases}

Following the normal convention for the empty product, $\backslash left(\backslash frac\{a\}\{1\}\backslash right)\; =\; 1.$

ω(n), defined above as the number of distinct primes dividing n, is additive (see Prime omega function).

Ω(n), defined above as the number of prime factors of n counted with multiplicities, is completely additive (see Prime omega function).

For a fixed prime p, ν_p(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

=== Logarithmic derivative ===

$\backslash operatorname\{ld\}(n)=\backslash frac\{D(n)\}\{n\}\; =\; \backslash sum\_\{\backslash stackrel\{p\backslash mid\; n\}\{p\backslash text\{\; prime\}\}\}\; \backslash frac\; \{v\_p(n)\}\; \{p\}$, where $D(n)$ is the arithmetic derivative.

These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

π(x), the prime-counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers.

$$\backslash pi(x)\; =\; \backslash sum\_\{p\; \backslash le\; x\}\; 1$$

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, etc. It is the summation function of the arithmetic function which takes the value 1/k on integers which are the kth power of some prime number, and the value 0 on other integers.

$$\backslash Pi(x)\; =\; \backslash sum\_\{p^k\backslash le\; x\}\backslash frac\{1\}\{k\}.$$

ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x.

$$\backslash vartheta(x)=\backslash sum\_\{p\backslash le\; x\}\; \backslash log\; p,$$

$$\backslash psi(x)\; =\; \backslash sum\_\{p^k\backslash le\; x\}\; \backslash log\; p.$$

The second Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

Λ(n), the von Mangoldt function, is 0 unless the argument n is a prime power {{math|p^k}}, in which case it is the natural logarithm of the prime p:

$$\backslash Lambda(n)\; =\; \backslash begin\{cases\}$$

\log p &\text{if } n = 2,3,4,5,7,8,9,11,13,16,\ldots=p^k \text{ is a prime power}\\

0&\text{if } n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;\text{ is not a prime power}.

\end{cases}

p(n), the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:

λ(n), the Carmichael function, is the smallest positive number such that $a^\{\backslash lambda(n)\}\backslash equiv\; 1\; \backslash pmod\{n\}$   for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n:

$$\backslash lambda(n)\; =\; \backslash begin\{cases\}$$

\;\;\phi(n) &\text{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\

\tfrac 1 2 \phi(n)&\text{if }n=8,16,32,64,\dots

\end{cases}

and for general n it is the least common multiple of λ of each of the prime power factors of n:

$$\backslash lambda(p\_1^\{a\_1\}p\_2^\{a\_2\}\; \backslash dots\; p\_\{\backslash omega(n)\}^\{a\_\{\backslash omega(n)\}\})\; =\; \backslash operatorname\{lcm\}[\backslash lambda(p\_1^\{a\_1\}),\backslash ;\backslash lambda(p\_2^\{a\_2\}),\backslash dots,\backslash lambda(p\_\{\backslash omega(n)\}^\{a\_\{\backslash omega(n)\}\})\; ].$$

h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

r_k(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

$$r\_k(n)\; =\; \backslash left|\backslash left\backslash \{(a\_1,\; a\_2,\backslash dots,a\_k):n=a\_1^2+a\_2^2+\backslash cdots+a\_k^2\backslash right\backslash \}\backslash right|$$

Using the Heaviside notation for the derivative, the arithmetic derivative D(n) is a function such that

• $D(n)\; =\; 1$ if n prime, and
• $D(mn)\; =\; m\; D(n)\; +\; D(m)\; n$ (the product rule)

Given an arithmetic function a(n), its summation function A(x) is defined by

$$A(x)\; :=\; \backslash sum\_\{n\; \backslash le\; x\}\; a(n)\; .$$

A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:

Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find asymptotic behaviour for the summation function for large x.

A classical example of this phenomenonHardy & Wright, §§ 18.1–18.2 is given by the divisor summatory function, the summation function of d(n), the number of divisors of n:

$$\backslash liminf\_\{n\backslash to\backslash infty\}\; d(n)\; =\; 2$$

$$\backslash limsup\_\{n\backslash to\backslash infty\}\backslash frac\{\backslash log\; d(n)\; \backslash log\backslash log\; n\}\{\backslash log\; n\}\; =\; \backslash log\; 2$$

$$\backslash lim\_\{n\backslash to\backslash infty\}\backslash frac\{d(1)\; +\; d(2)+\; \backslash cdots\; +d(n)\}\{\backslash log(1)\; +\; \backslash log(2)+\; \backslash cdots\; +\backslash log(n)\}\; =\; 1.$$

An average order of an arithmetic function is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if

$$\backslash sum\_\{n\; \backslash le\; x\}\; f(n)\; \backslash sim\; \backslash sum\_\{n\; \backslash le\; x\}\; g(n)$$

as x tends to infinity. The example above shows that d(n) has the average order log(n).{{cite book | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=Cambridge University Press | pages=36–55 | year=1995 | isbn=0-521-41261-7 }}

Given an arithmetic function a(n), let F_a(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.

$$F\_a(s)\; :=\; \backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{a(n)\}\{n^s\}\; .$$

F_a(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the Riemann zeta function.

The generating function of the Möbius function is the inverse of the zeta function:

$$\backslash zeta(s)\backslash ,\backslash sum\_\{n=1\}^\backslash infty\backslash frac\{\backslash mu(n)\}\{n^s\}=1,\; \backslash ;\backslash ;\backslash Re\; s\; >1.$$

Consider two arithmetic functions a and b and their respective generating functions F_a(s) and F_b(s). The product F_a(s)F_b(s) can be computed as follows:

$$F\_a(s)F\_b(s)\; =\; \backslash left(\; \backslash sum\_\{m=1\}^\{\backslash infty\}\backslash frac\{a(m)\}\{m^s\}\; \backslash right)\backslash left(\; \backslash sum\_\{n=1\}^\{\backslash infty\}\backslash frac\{b(n)\}\{n^s\}\; \backslash right)\; .$$

It is a straightforward exercise to show that if c(n) is defined by

$$c(n)\; :=\; \backslash sum\_\{ij\; =\; n\}\; a(i)b(j)\; =\; \backslash sum\_\{i\backslash mid\; n\}a(i)b\backslash left(\backslash frac\{n\}\{i\}\backslash right)\; ,$$

then $$F\_c(s)\; =\; F\_a(s)\; F\_b(s).$$

This function c is called the Dirichlet convolution of a and b, and is denoted by $a*b$.

A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function:

$$g(n)\; =\; \backslash sum\_\{d\; \backslash mid\; n\}f(d).$$

Multiplying by the inverse of the zeta function gives the Möbius inversion formula:

$$f(n)\; =\; \backslash sum\_\{d\backslash mid\; n\}\backslash mu\backslash left(\backslash frac\{n\}\{d\}\backslash right)g(d).$$

If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page divisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.

Here are a few examples:

: $$

\sum_{\delta\mid n}\mu(\delta)=

\sum_{\delta\mid n}\lambda\left(\frac{n}{\delta}\right)|\mu(\delta)|=

\begin{cases}

1 & \text{if } n=1\\

0 & \text{if } n\ne1

\end{cases}

    where λ is the Liouville function.Hardy & Wright, Thm. 263

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash varphi(\backslash delta)\; =\; n.$      Hardy & Wright, Thm. 63

:: $\backslash varphi(n)$

=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta

=n\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta}.

      Möbius inversion

: $\backslash sum\_\{d\; \backslash mid\; n\; \}\; J\_k(d)\; =\; n^k.$      see references at Jordan's totient function

:: $$

J_k(n)

=\sum_{\delta\mid n}\mu\left(\frac{n}{\delta}\right)\delta^k

=n^k\sum_{\delta\mid n}\frac{\mu(\delta)}{\delta^k}.

      Möbius inversion

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash delta^sJ\_r(\backslash delta)J\_s\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)\; =\; J\_\{r+s\}(n)$      Holden et al. in external links The formula is Gegenbauer's

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash varphi(\backslash delta)d\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)\; =\; \backslash sigma(n).$      Hardy & Wright, Thm. 288–290Dineva in external links, prop. 4

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}|\backslash mu(\backslash delta)|\; =\; 2^\{\backslash omega(n)\}.$      Hardy & Wright, Thm. 264

:: $|\backslash mu(n)|=\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash mu\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)2^\{\backslash omega(\backslash delta)\}.$       Möbius inversion

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}2^\{\backslash omega(\backslash delta)\}=d(n^2).$      

:: $2^\{\backslash omega(n)\}=\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash mu\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)d(\backslash delta^2).$       Möbius inversion

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}d(\backslash delta^2)=d^2(n).$      

:: $d(n^2)=\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash mu\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)d^2(\backslash delta).$       Möbius inversion

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}d\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)2^\{\backslash omega(\backslash delta)\}=d^2(n).$      

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash lambda(\backslash delta)=\backslash begin\{cases\}$

&1\text{ if } n \text{ is a square }\\

&0\text{ if } n \text{ is not square.}

\end{cases}     where λ is the Liouville function.

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash Lambda(\backslash delta)\; =\; \backslash log\; n.$      Hardy & Wright, Thm. 296

:: $\backslash Lambda(n)=\backslash sum\_\{\backslash delta\backslash mid\; n\}\backslash mu\backslash left(\backslash frac\{n\}\{\backslash delta\}\backslash right)\backslash log(\backslash delta).$       Möbius inversion

For all $k\; \backslash ge\; 4,\backslash ;\backslash ;\backslash ;\; r\_k(n)\; >\; 0.$     (Lagrange's four-square theorem).

: $$

r_2(n) = 4\sum_{d\mid n}\left(\frac{-4}{d}\right),

Hardy & Wright, Thm. 278

where the Kronecker symbol has the values

: $$

\left(\frac{-4}{n}\right) =

\begin{cases}

+1&\text{if }n\equiv 1 \pmod 4 \\

-1&\text{if }n\equiv 3 \pmod 4\\

\;\;\;0&\text{if }n\text{ is even}.\\

\end{cases}

There is a formula for r₃ in the section on class numbers below.

r_4(n) =

8 \sum_{\stackrel{d\mid n}{ 4\, \nmid \,d}}d =

8 (2+(-1)^n)\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d =

\begin{cases}

8\sigma(n)&\text{if } n \text{ is odd }\\

24\sigma\left(\frac{n}{2^\nu}\right)&\text{if } n \text{ is even }

\end{cases},

where {{math|1=ν = ν₂(n)}}.    Hardy & Wright, Thm. 386Hardy, Ramanujan, eqs 9.1.2, 9.1.3Koblitz, Ex. III.5.2

$$r\_6(n)\; =\; 16\; \backslash sum\_\{d\backslash mid\; n\}\; \backslash chi\backslash left(\backslash frac\{n\}\{d\}\backslash right)d^2\; -\; 4\backslash sum\_\{d\backslash mid\; n\}\; \backslash chi(d)d^2,$$

where $\backslash chi(n)\; =\; \backslash left(\backslash frac\{-4\}\{n\}\backslash right).$Hardy & Wright, § 20.13

Define the function {{math|1=σ_k^*(n)}} asHardy, Ramanujan, § 9.7

$$\backslash sigma\_k^*(n)\; =\; (-1)^\{n\}\backslash sum\_\{d\backslash mid\; n\}(-1)^d\; d^k=$$

\begin{cases}

\sum_{d\mid n} d^k=\sigma_k(n)&\text{if } n \text{ is odd }\\

\sum_{\stackrel{d\mid n}{ 2\, \mid \,d}}d^k -\sum_{\stackrel{d\mid n}{ 2\, \nmid \,d}}d^k&\text{if } n \text{ is even}.

\end{cases}

That is, if n is odd, {{math|1=σ_k^*(n)}} is the sum of the kth powers of the divisors of n, that is, {{math|1=σ_k(n),}} and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

: $r\_8(n)\; =\; 16\backslash sigma\_3^*(n).$    Hardy, Ramanujan, § 9.13

Adopt the convention that Ramanujan's {{math|1=τ(x) = 0}} if x is not an integer.

: $$

r_{24}(n) = \frac{16}{691}\sigma_{11}^*(n) + \frac{128}{691}\left\{

(-1)^{n-1}259\tau(n)-512\tau\left(\frac{n}{2}\right)\right\}

   Hardy, Ramanujan, § 9.17

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

: $\backslash left(\backslash sum\_\{n=0\}^\backslash infty\; a\_n\; x^n\backslash right)\backslash left(\backslash sum\_\{n=0\}^\backslash infty\; b\_n\; x^n\backslash right)$

= \sum_{i=0}^\infty \sum_{j=0}^\infty a_i b_j x^{i+j}

= \sum_{n=0}^\infty \left(\sum_{i=0}^n a_i b_{n-i}\right) x^n

= \sum_{n=0}^\infty c_n x^n

.

The sequence $c\_n\; =\; \backslash sum\_\{i=0\}^n\; a\_i\; b\_\{n-i\}$ is called the convolution or the Cauchy product of the sequences a_n and b_n.

{{br}}These formulas may be proved analytically (see Eisenstein series) or by elementary methods.Williams, ch. 13; Huard, et al. (external links).

: $$

\sigma_3(n) = \frac{1}{5}\left\{6n\sigma_1(n)-\sigma_1(n) + 12\sum_{0

   Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146

: $$

\sigma_5(n) = \frac{1}{21}\left\{10(3n-1)\sigma_3(n)+\sigma_1(n) + 240\sum_{0

   Koblitz, ex. III.2.8

: $$

\begin{align}

\sigma_7(n)

&=\frac{1}{20}\left\{21(2n-1)\sigma_5(n)-\sigma_1(n) + 504\sum_{0

&=\sigma_3(n) + 120\sum_{0

\end{align}

   Koblitz, ex. III.2.3

: $$

\begin{align}

\sigma_9(n)

&= \frac{1}{11}\left\{10(3n-2)\sigma_7(n)+\sigma_1(n) + 480\sum_{0

&= \frac{1}{11}\left\{21\sigma_5(n)-10\sigma_3(n) + 5040\sum_{0

\end{align}

   Koblitz, ex. III.2.2

: $$

\tau(n) = \frac{65}{756}\sigma_{11}(n) + \frac{691}{756}\sigma_{5}(n) - \frac{691}{3}\sum_{0

    where τ(n) is Ramanujan's function.    Koblitz, ex. III.2.4Apostol, Modular Functions ..., Ex. 6.10

Since σ_k(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruencesApostol, Modular Functions..., Ch. 6 Ex. 10 for the functions. See Ramanujan tau function for some examples.

Extend the domain of the partition function by setting {{math|1=p(0) = 1.}}

: $$

p(n)=\frac{1}{n}\sum_{1\le k\le n}\sigma(k)p(n-k).

   G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279   This recurrence can be used to compute p(n).

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number h of quadratic number fields to the Jacobi symbol.Landau, p. 168, credits Gauss as well as Dirichlet

An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).Cohen, Def. 5.1.2

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol:

$$\backslash left(\backslash frac\{a\}\{2\}\backslash right)\; =\; \backslash begin\{cases\}$$

\;\;\,0&\text{ if } a \text{ is even}

\\(-1)^{\frac{a^2-1}{8}}&\text{ if }a \text{ is odd. }

\end{cases}

Then if D < −4 is a fundamental discriminantCohen, Corr. 5.3.13see Edwards, § 9.5 exercises for more complicated formulas.

$$\backslash begin\{align\}$$

h(D) & = \frac{1}{D} \sum_{r=1}^

& = \frac{1}{2-\left(\tfrac{D}{2}\right)} \sum_{r=1}^{|D|/2}\left(\frac{D}{r}\right).

\end{align}

There is also a formula relating r₃ and h. Again, let D be a fundamental discriminant, D < −4. ThenCohen, Prop 5.3.10

$$r\_3(|D|)\; =\; 12\backslash left(1-\backslash left(\backslash frac\{D\}\{2\}\backslash right)\backslash right)h(D).$$

Let $H\_n\; =\; 1\; +\; \backslash frac\; 1\; 2\; +\; \backslash frac\; 1\; 3\; +\; \backslash cdots\; +\backslash frac\{1\}\{n\}$   be the nth harmonic number. Then

: $\backslash sigma(n)\; \backslash le\; H\_n\; +\; e^\{H\_n\}\backslash log\; H\_n$   is true for every natural number n if and only if the Riemann hypothesis is true.    See Divisor function.

The Riemann hypothesis is also equivalent to the statement that, for all n > 5040,

(where γ is the Euler–Mascheroni constant). This is Robin's theorem.

: $\backslash sum\_\{p\}\backslash nu\_p(n)\; =\; \backslash Omega(n).$

: $\backslash psi(x)=\backslash sum\_\{n\backslash le\; x\}\backslash Lambda(n).$    Hardy & Wright, eq. 22.1.2

: $\backslash Pi(x)=\; \backslash sum\_\{n\backslash le\; x\}\backslash frac\{\backslash Lambda(n)\}\{\backslash log\; n\}.$    See prime-counting functions.

: $e^\{\backslash theta(x)\}=\backslash prod\_\{p\backslash le\; x\}p.$    Hardy & Wright, eq. 22.1.1

: $e^\{\backslash psi(x)\}=\; \backslash operatorname\{lcm\}[1,2,\backslash dots,\backslash lfloor\; x\backslash rfloor].$    Hardy & Wright, eq. 22.1.3

In 1965 P Kesava Menon provedLászló Tóth, Menon's Identity and Arithmetical Sums ..., eq. 1

$$\backslash sum\_\{\backslash stackrel\{1\backslash le\; k\backslash le\; n\}\{\; \backslash gcd(k,n)=1\}\}\; \backslash gcd(k-1,n)=\backslash varphi(n)d(n).$$

This has been generalized by a number of mathematicians. For example,

• B. SuryTóth, eq. 5 $$$$

\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,n)=1}} \gcd(k_1-1,k_2,\dots,k_s,n)

= \varphi(n)\sigma_{s-1}(n).

• N. RaoTóth, eq. 3 $$$$

\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{ \gcd(k_1,k_2,\dots,k_s,n)=1}} \gcd(k_1-a_1,k_2-a_2,\dots,k_s-a_s,n)^s

=J_s(n)d(n), where a₁, a₂, ..., a_s are integers, gcd(a₁, a₂, ..., a_s, n) = 1.

• László Fejes TóthTóth, eq. 35 $$$$

\sum_{\stackrel{1\le k\le m}{ \gcd(k,m)=1}} \gcd(k^2-1,m_1)\gcd(k^2-1,m_2)

=\varphi(n)\sum_{\stackrel{d_1\mid m_1} {d_2\mid m_2}} \varphi(\gcd(d_1, d_2))2^{\omega(\operatorname{lcm}(d_1, d_2))},

where m₁ and m₂ are odd, m = lcm(m₁, m₂).

In fact, if f is any arithmetical functionTóth, eq. 2Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f.

$$\backslash sum\_\{\backslash stackrel\{1\backslash le\; k\backslash le\; n\}\{\; \backslash gcd(k,n)=1\}\}\; f(\backslash gcd(k-1,n))$$

=\varphi(n)\sum_{d\mid n}\frac{(\mu*f)(d)}{\varphi(d)},

where $*$ stands for Dirichlet convolution.

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity:

$$\backslash left(\backslash frac\{m\}\{n\}\backslash right)\; \backslash left(\backslash frac\{n\}\{m\}\backslash right)\; =\; (-1)^\{(m-1)(n-1)/4\}.$$

Let D(n) be the arithmetic derivative. Then the logarithmic derivative $$\backslash frac\{D(n)\}\{n\}\; =\; \backslash sum\_\{\backslash stackrel\{p\backslash mid\; n\}\{p\backslash text\{\; prime\}\}\}\; \backslash frac\; \{v\_\{p\}(n)\}\; \{p\}.$$ See Arithmetic derivative for details.

Let λ(n) be Liouville's function. Then

: $|\backslash lambda(n)|\backslash mu(n)\; =\backslash lambda(n)|\backslash mu(n)|\; =\; \backslash mu(n),$     and

: $\backslash lambda(n)\backslash mu(n)\; =\; |\backslash mu(n)|\; =\backslash mu^2(n).$    

Let λ(n) be Carmichael's function. Then

: $\backslash lambda(n)\backslash mid\; \backslash phi(n).$     Further,

: $\backslash lambda(n)=\; \backslash phi(n)\; \backslash text\{\; if\; and\; only\; if\; \}n=\backslash begin\{cases\}$

1,2, 4;\\

3,5,7,9,11, \ldots \text{ (that is, } p^k \text{, where }p\text{ is an odd prime)};\\

6,10,14,18,\ldots \text{ (that is, } 2p^k\text{, where }p\text{ is an odd prime)}.

\end{cases}

See Multiplicative group of integers modulo n and Primitive root modulo n.

: $2^\{\backslash omega(n)\}\; \backslash le\; d(n)\; \backslash le\; 2^\{\backslash Omega(n)\}.$    Hardy Ramanujan, eq. 3.10.3Hardy & Wright, § 22.13

:    Hardy & Wright, Thm. 329

: $\backslash begin\{align\}$

c_q(n)

&=\frac{\mu\left(\frac{q}{\gcd(q, n)}\right)}{\phi\left(\frac{q}{\gcd(q, n)}\right)}\phi(q)\\

&=\sum_{\delta\mid \gcd(q,n)}\mu\left(\frac{q}{\delta}\right)\delta.

\end{align}    Hardy & Wright, Thms. 271, 272     Note that  $\backslash phi(q)\; =\; \backslash sum\_\{\backslash delta\backslash mid\; q\}\backslash mu\backslash left(\backslash frac\{q\}\{\backslash delta\}\backslash right)\backslash delta.$    Hardy & Wright, eq. 16.3.1

: $c\_q(1)\; =\; \backslash mu(q).$

: $c\_q(q)\; =\; \backslash phi(q).$

: $\backslash sum\_\{\backslash delta\backslash mid\; n\}d^\{3\}(\backslash delta)\; =\; \backslash left(\backslash sum\_\{\backslash delta\backslash mid\; n\}d(\backslash delta)\backslash right)^2.$    Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.   Compare this with {{math|1=1³ + 2³ + 3³ + ... + n³ = (1 + 2 + 3 + ... + n)²}}

: $d(uv)\; =\; \backslash sum\_\{\backslash delta\backslash mid\; \backslash gcd(u,v)\}\backslash mu(\backslash delta)d\backslash left(\backslash frac\{u\}\{\backslash delta\}\backslash right)d\backslash left(\backslash frac\{v\}\{\backslash delta\}\backslash right).$

   Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134

: $\backslash sigma\_k(u)\backslash sigma\_k(v)\; =\; \backslash sum\_\{\backslash delta\backslash mid\; \backslash gcd(u,v)\}\backslash delta^k\backslash sigma\_k\backslash left(\backslash frac\{uv\}\{\backslash delta^2\}\backslash right).$

   Apostol, Modular Functions ..., ch. 6 eq. 4

: $\backslash tau(u)\backslash tau(v)\; =\; \backslash sum\_\{\backslash delta\backslash mid\; \backslash gcd(u,v)\}\backslash delta^\{11\}\backslash tau\backslash left(\backslash frac\{uv\}\{\backslash delta^2\}\backslash right),$

    where τ(n) is Ramanujan's function.    Apostol, Modular Functions ..., ch. 6 eq. 3

{{reflist|30em}}

• {{citation

|title=Introduction to Analytic Number Theory

|author=Tom M. Apostol |author-link=Tom M. Apostol

|year=1976

|publisher=Springer Undergraduate Texts in Mathematics

|isbn=0-387-90163-9

|url-access=registration

|url=https://archive.org/details/introductiontoan00apos_0

}}

• {{citation

|last = Apostol |first = Tom M. |author-link = Tom M. Apostol

|title = Modular Functions and Dirichlet Series in Number Theory (2nd Edition)

|publisher = Springer

|location = New York

|year = 1989

|isbn = 0-387-97127-0

|url-access = registration

|url = https://archive.org/details/modularfunctions0000apos

}}

• {{citation | first1 = Paul T. | last1 = Bateman |author-link1=Paul T. Bateman | first2 = Harold G. | last2 = Diamond | year = 2004 | title = Analytic number theory, an introduction | publisher = World Scientific | isbn = 978-981-238-938-1 }}
• {{citation

| last1 = Cohen | first1 = Henri |author-link=Henri Cohen (number theorist)

| title = A Course in Computational Algebraic Number Theory

| publisher = Springer

| location = Berlin

| year = 1993

| isbn = 3-540-55640-0

}}

• {{cite book

| last = Edwards

| first = Harold

| author-link = Harold Edwards (mathematician)

| title = Fermat's Last Theorem

| publisher = Springer

| location = New York

| year = 1977

| isbn = 0-387-90230-9

}}

• {{citation

| author1-link = G. H. Hardy

| last1 = Hardy | first1 = G. H.

| title = Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work

| publisher = AMS / Chelsea

| location = Providence RI

| year = 1999

| isbn = 978-0-8218-2023-0| hdl = 10115/1436

}}

• {{Hardy and Wright|edition=5th}}
• {{citation

|title=The Prime Number Theorem

|first=G. J. O. | last=Jameson

|year=2003

|publisher=Cambridge University Press

|isbn=0-521-89110-8

}}

• {{citation

| last1 = Koblitz | first1 = Neal

| title = Introduction to Elliptic Curves and Modular Forms

| publisher = Springer

| location = New York

| year = 1984

| isbn = 0-387-97966-2

}}

• {{citation

| last1 = Landau | first1 = Edmund |author-link=Edmund Landau

| title = Elementary Number Theory

| publisher = Chelsea

| location = New York

| year = 1966

}}

• {{citation

|title=Fundamentals of Number Theory

|author=William J. LeVeque |author-link=William J. LeVeque

|year=1996

|publisher=Courier Dover Publications

|isbn=0-486-68906-9

}}

• {{citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = D. C. Heath and Company | location = Lexington | lccn = 77-171950 }}
• {{citation

|title=Introduction to Mathematical Logic

|author=Elliott Mendelson

|year=1987

|publisher=CRC Press

|isbn=0-412-80830-7}}

• {{citation

| last = Nagell | first = Trygve |author-link=Trygve Nagell

| title = Introduction to number theory (2nd Edition)

| publisher = Chelsea

| year = 1964

| isbn = 978-0-8218-2833-5

}}

• {{citation | first1 = Ivan M. | last1 = Niven|author-link1=Ivan M. Niven | first2 = Herbert S. | last2 = Zuckerman | year = 1972 | title = An introduction to the theory of numbers (3rd Edition) | publisher = John Wiley & Sons | isbn = 0-471-64154-5 }}
• {{citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = Prentice Hall | location = Englewood Cliffs | lccn = 77-81766 }}
• {{citation

| last1 = Ramanujan | first1 = Srinivasa

| title = Collected Papers

| publisher = AMS / Chelsea

| location = Providence RI

| year = 2000

| isbn = 978-0-8218-2076-6

}}

• {{citation | last=Williams | first=Kenneth S. | title=Number theory in the spirit of Liouville | zbl=1227.11002 | series=London Mathematical Society Student Texts | volume=76 | location=Cambridge | publisher=Cambridge University Press | isbn=978-0-521-17562-3 | year=2011 }}

• {{citation | first1=Wolfgang | last1=Schwarz | first2=Jürgen | last2=Spilker | title=Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties | year=1994 | publisher=Cambridge University Press | isbn=0-521-42725-8 | zbl=0807.11001 | series=London Mathematical Society Lecture Note Series | volume=184 }}

• {{springer|title=Arithmetic function|id=p/a013300}}
• Matthew Holden, Michael Orrison, Michael Varble [https://web.archive.org/web/20160305132124/https://www.math.hmc.edu/~orrison/research/papers/totient.pdf Yet another Generalization of Euler's Totient Function]
• Huard, Ou, Spearman, and Williams. [http://mathstat.carleton.ca/~williams/papers/pdf/249.pdf Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions]
• Dineva, Rosica, [http://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf The Euler Totient, the Möbius, and the Divisor Functions] {{webarchive|url=https://web.archive.org/web/20210116061553/https://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf |date=2021-01-16 }}
• László Tóth, [https://arxiv.org/PS_cache/arxiv/pdf/1103/1103.5861v2.pdf Menon's Identity and arithmetical sums representing functions of several variables]

{{Classes of natural numbers|collapsed}}

{{Authority control}}

Category:Functions and mappings