In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of ''n''".
An example of an arithmetic function is the divisor function whose value at a positive integer ''n'' is equal to the number of divisors of ''n''.
There is a larger class of number-theoretic functions that do not fit the above definition, for example, the prime-counting functions. This article provides links to functions of both classes.
Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of Ramanujan's sum.

Multiplicative and additive 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''(''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''(''mn'') = ''a''(''m'')''a''(''n'') for all coprime natural numbers ''m'' and ''n''.

Notation

$\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$ :$\backslash prod\_p\; f(p)=\; f(2)f(3)f(5)\backslash cdots.$ Similarly, $\backslash sum\_\; f(p^k)$ and $\backslash prod\_\; f(p^k)$ mean that the sum or product is over all prime powers with strictly positive exponent (so ''k'' = 0 is not included): :$\backslash sum\_\; f(p^k)\; =\; \backslash sum\_p\backslash sum\_\; f(p^k)\; =\; f(2)\; +\; f(3)\; +\; f(4)\; +f(5)\; +f(7)+f(8)+f(9)+\backslash cdots$ $\backslash sum\_\; f(d)$ and $\backslash prod\_\; f(d)$ mean that the sum or product is over all positive divisors of ''n'', including 1 and ''n''. For example, if ''n'' = 12, :$\backslash prod\_\; f(d)\; =\; f(1)f(2)\; f(3)\; f(4)\; f(6)\; f(12).\backslash $ The notations can be combined: $\backslash sum\_\; f(p)$ and $\backslash prod\_\; f(p)$ mean that the sum or product is over all prime divisors of ''n''. For example, if ''n'' = 18, :$\backslash sum\_\; f(p)\; =\; f(2)\; +\; f(3),\backslash $ and similarly $\backslash sum\_\; f(p^k)$ and $\backslash prod\_\; f(p^k)$ mean that the sum or product is over all prime powers dividing ''n''. For example, if ''n'' = 24, :$\backslash prod\_\; f(p^k)\; =\; f(2)\; f(3)\; f(4)\; f(8).\backslash $

Ω(''n''), ''ω''(''n''), ''ν''_{''p''}(''n'') – prime power decomposition

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^\backslash cdots\; p\_k^$ where ''p''_{1} < ''p''_{2} < ... < ''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^.$
In terms of the above the prime omega functions ω and Ω are defined by
:''ω''(''n'') = ''k'',
:Ω(''n'') = ''a''_{1} + ''a''_{2} + ... + ''a''_{''k''}.
To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of ''n'' and the corresponding ''p''_{''i''}, ''a''_{''i''}, ω, and Ω.

Multiplicative functions

σ_{''k''}(''n''), τ(''n''), ''d''(''n'') – divisor sums

σ_{''k''}(''n'') is the sum of the ''k''th powers of the positive divisors of ''n'', including 1 and ''n'', where ''k'' is a complex number.
σ_{1}(''n''), the sum of the (positive) divisors of ''n'', is usually denoted by σ(''n'').
Since a positive number to the zero power is one, σ_{0}(''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\_^\; \backslash frac\; =\; \backslash prod\_^\; \backslash left(1\; +\; p\_i^k\; +\; p\_i^\; +\; \backslash cdots\; +\; p\_i^\backslash right).$
Setting ''k'' = 0 in the second product gives
:$\backslash tau(n)\; =\; d(n)\; =\; (1\; +\; a\_)(1+a\_)\backslash cdots(1+a\_).$

φ(''n'') – Euler totient function

φ(''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\_\; \backslash left(1-\backslash frac\backslash right)\; =n\; \backslash left(\backslash frac\backslash right)\backslash left(\backslash frac\backslash right)\; \backslash cdots\; \backslash left(\backslash frac\backslash right)\; .$

J_{''k''}(''n'') – Jordan totient function

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, .
:$J\_k(n)\; =\; n^k\; \backslash prod\_\; \backslash left(1-\backslash frac\backslash right)\; =n^k\; \backslash left(\backslash frac\backslash right)\backslash left(\backslash frac\backslash right)\; \backslash cdots\; \backslash left(\backslash frac\backslash right)\; .$

μ(''n'') – Möbius function

μ(''n''), the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below. :$\backslash mu(n)=\backslash begin\; (-1)^=(-1)^\; \&\backslash text\backslash ;\; \backslash omega(n)\; =\; \backslash Omega(n)\backslash \backslash \; 0\&\backslash text\backslash ;\backslash omega(n)\; \backslash ne\; \backslash Omega(n).\backslash end$ This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(''n'') – Ramanujan tau function

τ(''n''), the Ramanujan tau function, is defined by its generating function identity: :$\backslash sum\_\backslash tau(n)q^n=q\backslash prod\_(1-q^n)^.$ Although it is hard to say exactly what "arithmetical property of ''n''" it "expresses", (''τ''(''n'') is (2π)^{−12} times the ''n''th Fourier coefficient in the q-expansion of the modular discriminant function) 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

''c''_{''q''}(''n''), Ramanujan's sum, is the sum of the ''n''th powers of the primitive ''q''th roots of unity:
:$c\_q(n)=\; \backslash sum\_\; e^\; .$
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\_(n).$

''ψ''(''n'') - Dedekind psi function

The Dedekind psi function, used in the theory of modular functions, is defined by the formula :$\backslash psi(n)\; =\; n\; \backslash prod\_\backslash left(1+\backslash frac\backslash right).$

Completely multiplicative functions

λ(''n'') – Liouville function

''λ''(''n''), the Liouville function, is defined by :$\backslash lambda\; (n)\; =\; (-1)^.$

''χ''(''n'') – characters

All Dirichlet characters ''χ''(''n'') are completely multiplicative. Two characters have special notations: The principal character (mod ''n'') is denoted by ''χ''_{0}(''a'') (or ''χ''_{1}(''a'')). It is defined as
:$\backslash chi\_0(a)\; =\; \backslash begin\; 1\; \&\; \backslash text\; \backslash gcd(a,n)\; =\; 1,\; \backslash \backslash \; 0\; \&\; \backslash text\; \backslash gcd(a,n)\; \backslash ne\; 1.\; \backslash end$
The quadratic character (mod ''n'') is denoted by the Jacobi symbol for odd ''n'' (it is not defined for even ''n''.):
:$\backslash Bigg(\backslash frac\backslash Bigg)\; =\; \backslash left(\backslash frac\backslash right)^\backslash left(\backslash frac\backslash right)^\backslash cdots\; \backslash left(\backslash frac\backslash right)^.$
In this formula $(\backslash tfrac)$ is the Legendre symbol, defined for all integers ''a'' and all odd primes ''p'' by
:$\backslash left(\backslash frac\backslash right)\; =\; \backslash begin\; \backslash ;\backslash ;\backslash ,0\; \&\; \backslash text\; a\; \backslash equiv\; 0\; \backslash pmod\; p,\; \backslash \backslash +1\; \&\; \backslash texta\; \backslash not\backslash equiv\; 0\backslash pmod\; p\; \backslash textx,\; \backslash ;a\backslash equiv\; x^2\backslash pmod\; p\; \backslash \backslash -1\; \&\; \backslash text\; x.\; \backslash end$
Following the normal convention for the empty product, $\backslash left(\backslash frac\backslash right)\; =\; 1.$

Additive functions

''ω''(''n'') – distinct prime divisors

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

Completely additive functions

Ω(''n'') – prime divisors

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

''ν''_{''p''}(''n'') – ''p''-adic valuation of an integer ''n''

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

Neither multiplicative nor additive

(''x''), Π(''x''), ''θ''(''x''), ''ψ''(''x'') – prime count functions

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\_1$ A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ... It is the summation function of the arithmetic function which takes the value 1/''k'' on integers which are the k-th power of some prime number, and the value 0 on other integers. :$\backslash Pi(x)\; =\; \backslash sum\_\backslash frac.$ ''θ''(''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\_\; \backslash log\; p,$ :$\backslash psi(x)\; =\; \backslash sum\_\; \backslash log\; p.$ The Chebyshev function ''ψ''(''x'') is the summation function of the von Mangoldt function just below.

Λ(''n'') – von Mangoldt function

Λ(''n''), the von Mangoldt function, is 0 unless the argument ''n'' is a prime power , in which case it is the natural log of the prime ''p'': :$\backslash Lambda(n)\; =\; \backslash begin\backslash log\; p\; \&\backslash text\; n\; =\; 2,3,4,5,7,8,9,11,13,16,\backslash ldots=p^k\; \backslash text\backslash \backslash \; 0\&\backslash text\; n=1,6,10,12,14,15,18,20,21,\backslash dots\; \backslash ;\backslash ;\backslash ;\backslash ;\backslash text.\; \backslash end$

''p''(''n'') – partition function

''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: :$p(n)\; =\; |\backslash left\backslash |.$

λ(''n'') – Carmichael function

''λ''(''n''), the Carmichael function, is the smallest positive number such that $a^\backslash equiv\; 1\; \backslash pmod$ 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\; \backslash ;\backslash ;\backslash phi(n)\; \&\backslash textn\; =\; 2,3,4,5,7,9,11,13,17,19,23,25,27,\backslash dots\backslash \backslash \; \backslash tfrac12\backslash phi(n)\&\backslash textn=8,16,32,64,\backslash dots\; \backslash end$ and for general ''n'' it is the least common multiple of λ of each of the prime power factors of ''n'': :$\backslash lambda(p\_1^p\_2^\; \backslash dots\; p\_^)\; =\; \backslash operatornamelambda(p\_1^),\backslash ;\backslash lambda(p\_2^),\backslash dots,\backslash lambda(p\_^)$

''h''(''n'') – Class number

''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'') – Sum of ''k'' squares

''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 |$

''D''(''n'') – Arithmetic derivative

Using the Heaviside notation for the derivative, ''D''(''n'') is a function such that : $D(n)\; =\; 1$ if ''n'' prime, and : $D(mn)\; =\; m\; D(n)\; +\; D(m)\; n$ (Product rule)

** Summation functions **

Given an arithmetic function ''a''(''n''), its summation function ''A''(''x'') is defined by
:$A(x)\; :=\; \backslash sum\_\; 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:
:$A\_0(m)\; :=\; \backslash frac12\backslash left(\backslash sum\_\; a(n)\; +\backslash sum\_\; a(n)\backslash right)\; =\; A(m)\; -\; \backslash frac12\; a(m)\; .$
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 phenomenon is given by the divisor summatory function, the summation function of ''d''(''n''), the number of divisors of ''n'':
:$\backslash liminf\_d(n)\; =\; 2$
:$\backslash limsup\_\backslash frac\; =\; \backslash log\; 2$
:$\backslash lim\_\backslash frac\; =\; 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\_\; f(n)\; \backslash sim\; \backslash sum\_\; g(n)$
as ''x'' tends to infinity. The example above shows that ''d''(''n'') has the average order log(''n'').

Dirichlet convolution

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):
:$F\_a(s)\; :=\; \backslash sum\_^\backslash infty\; \backslash frac\; .$
''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\_^\backslash infty\backslash frac=1,\; \backslash ;\backslash ;\backslash mathfrak\; \backslash ,s\; >0.$
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\_^\backslash frac\; \backslash right)\backslash left(\; \backslash sum\_^\backslash frac\; \backslash right)\; .$
It is a straightforward exercise to show that if ''c''(''n'') is defined by
:$c(n)\; :=\; \backslash sum\_\; a(i)b(j)\; =\; \backslash sum\_a(i)b\backslash left(\backslash frac\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\_f(d).$
Multiplying by the inverse of the zeta function gives the Möbius inversion formula:
:$f(n)\; =\; \backslash sum\_\backslash mu\backslash left(\backslash frac\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.

Relations among the functions

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:

Dirichlet convolutions

:$\backslash sum\_\backslash mu(\backslash delta)=\; \backslash sum\_\backslash lambda\backslash left(\backslash frac\backslash right)|\backslash mu(\backslash delta)|=\; \backslash begin\; 1\; \&\; \backslash text\; n=1\backslash \backslash \; 0\; \&\; \backslash text\; n\backslash ne1\; \backslash end$ where ''λ'' is the Liouville function. :$\backslash sum\_\backslash varphi(\backslash delta)\; =\; n.$ ::$\backslash varphi(n)\; =\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta\; =n\backslash sum\_\backslash frac.$ Möbius inversion :$\backslash sum\_\; J\_k(d)\; =\; n^k.$ ::$J\_k(n)\; =\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta^k\; =n^k\backslash sum\_\backslash frac.$ Möbius inversion :$\backslash sum\_\backslash delta^sJ\_r(\backslash delta)J\_s\backslash left(\backslash frac\backslash right)\; =\; J\_(n)$ :$\backslash sum\_\backslash varphi(\backslash delta)d\backslash left(\backslash frac\backslash right)=\; \backslash sigma(n).$ :$\backslash sum\_|\backslash mu(\backslash delta)|=\; 2^.$ ::$|\backslash mu(n)|=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)2^.$ Möbius inversion :$\backslash sum\_2^=\; d(n^2).$ ::$2^=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)d(\backslash delta^2).$ Möbius inversion :$\backslash sum\_d(\backslash delta^2)=\; d^2(n).$ ::$d(n^2)=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)d^2(\backslash delta).$ Möbius inversion :$\backslash sum\_d\backslash left(\backslash frac\backslash right)2^=\; d^2(n).$ :$\backslash sum\_\backslash lambda(\backslash delta)=\backslash begin\; \&1\backslash text\; n\; \backslash text\backslash \backslash \; \&0\backslash text\; n\; \backslash text\; \backslash end$ where λ is the Liouville function. :$\backslash sum\_\backslash Lambda(\backslash delta)\; =\; \backslash log\; n.$ ::$\backslash Lambda(n)=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash log(\backslash delta).$ Möbius inversion

Sums of squares

For all $k\; \backslash ge\; 4,\backslash ;\backslash ;\backslash ;\; r\_k(n)\; >\; 0.$ (Lagrange's four-square theorem). : :$r\_2(n)\; =\; 4\backslash sum\_\backslash left(\backslash frac\backslash right),$ where the Kronecker symbol has the values :$\backslash left(\backslash frac\backslash right)\; =\; \backslash begin\; +1\&\backslash textn\backslash equiv\; 1\; \backslash pmod\; 4\; \backslash \backslash \; -1\&\backslash textn\backslash equiv\; 3\; \backslash pmod\; 4\backslash \backslash \; \backslash ;\backslash ;\backslash ;0\&\backslash textn\backslash text.\backslash \backslash \; \backslash end$ There is a formula for r_{3} in the section on class numbers below.
:$r\_4(n)\; =\; 8\; \backslash sum\_d\; =\; 8\; (2+(-1)^n)\backslash sum\_d\; =\; \backslash begin\; 8\backslash sigma(n)\&\backslash text\; n\; \backslash text\backslash \backslash \; 24\backslash sigma\backslash left(\backslash frac\backslash right)\&\backslash text\; n\; \backslash text\; \backslash end,$
where ''ν'' = ''ν''_{2}(''n'').
:$r\_6(n)\; =\; 16\; \backslash sum\_\; \backslash chi\backslash left(\backslash frac\backslash right)d^2\; -\; 4\backslash sum\_\; \backslash chi(d)d^2,$
where $\backslash chi(n)\; =\; \backslash left(\backslash frac\backslash right).$Hardy & Wright, § 20.13
Define the function σ_{''k''}^{*}(''n'') as
:$\backslash sigma\_k^*(n)\; =\; (-1)^\backslash sum\_(-1)^d\; d^k=\; \backslash begin\; \backslash sum\_\; d^k=\backslash sigma\_k(n)\&\backslash text\; n\; \backslash text\backslash \backslash \; \backslash sum\_d^k\; -\backslash sum\_d^k\&\backslash text\; n\; \backslash text.\; \backslash end$
That is, if ''n'' is odd, σ_{''k''}^{*}(''n'') is the sum of the ''k''th powers of the divisors of ''n'', that is, σ_{''k''}(''n''), and if ''n'' is even it is the sum of the ''k''th powers of the even divisors of ''n'' minus the sum of the ''k''th powers of the odd divisors of ''n''.
:$r\_8(n)\; =\; 16\backslash sigma\_3^*(n).$
Adopt the convention that Ramanujan's ''τ''(''x'') = 0 if ''x'' is not an integer.
:$r\_(n)\; =\; \backslash frac\backslash sigma\_^*(n)\; +\; \backslash frac\backslash left\backslash $

Divisor sum convolutions

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\_^\backslash infty\; a\_n\; x^n\backslash right)\backslash left(\backslash sum\_^\backslash infty\; b\_n\; x^n\backslash right)\; =\; \backslash sum\_^\backslash infty\; \backslash sum\_^\backslash infty\; a\_i\; b\_j\; x^\; =\; \backslash sum\_^\backslash infty\; \backslash left(\backslash sum\_^n\; a\_i\; b\_\backslash right)\; x^n\; =\; \backslash sum\_^\backslash infty\; c\_n\; x^n\; .$ The sequence $c\_n\; =\; \backslash sum\_^n\; a\_i\; b\_$ is called the convolution or the Cauchy product of the sequences ''a''_{''n''} and ''b''_{''n''}.

These formulas may be proved analytically (see Eisenstein series) or by elementary methods. :$\backslash sigma\_3(n)\; =\; \backslash frac\backslash left\backslash .$ Ramanujan, ''On Certain Arithmetical Functions'', Table IV; ''Papers'', p. 146 :$\backslash sigma\_5(n)\; =\; \backslash frac\backslash left\backslash .$ Koblitz, ex. III.2.8 :$\backslash begin\; \backslash sigma\_7(n)\; \&=\backslash frac\backslash left\backslash \backslash \backslash \; \&=\backslash sigma\_3(n)\; +\; 120\backslash sum\_\backslash sigma\_3(k)\backslash sigma\_3(n-k).\; \backslash end$ :$\backslash begin\; \backslash sigma\_9(n)\; \&=\; \backslash frac\backslash left\backslash \backslash \backslash \; \&=\; \backslash frac\backslash left\backslash .\; \backslash end$ :$\backslash tau(n)\; =\; \backslash frac\backslash sigma\_(n)\; +\; \backslash frac\backslash sigma\_(n)\; -\; \backslash frac\backslash sum\_\backslash sigma\_5(k)\backslash sigma\_5(n-k),$ where ''τ''(''n'') is Ramanujan's function. Since ''σ''_{''k''}(''n'') (for natural number ''k'') and ''τ''(''n'') are integers, the above formulas can be used to prove congruences for the functions. See Ramanujan tau function for some examples.
Extend the domain of the partition function by setting ''p''(0) = 1.
:$p(n)=\backslash frac\backslash sum\_\backslash sigma(k)p(n-k).$ This recurrence can be used to compute ''p''(''n'').

Class number related

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number ''h'' of quadratic number fields to the Jacobi symbol. 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). Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol: :$\backslash left(\backslash frac\backslash right)\; =\; \backslash begin\; \backslash ;\backslash ;\backslash ,0\&\backslash text\; a\; \backslash text\; \backslash \backslash (-1)^\&\backslash texta\; \backslash text\; \backslash end$ Then if ''D'' < −4 is a fundamental discriminant :$\backslash begin\; h(D)\; \&\; =\; \backslash frac\; \backslash sum\_^r\backslash left(\backslash frac\backslash right)\backslash \backslash \; \&\; =\; \backslash frac\; \backslash sum\_^\backslash left(\backslash frac\backslash right).\; \backslash end$ There is also a formula relating ''r''_{3} and ''h''. Again, let ''D'' be a fundamental discriminant, ''D'' < −4. Then
:$r\_3(|D|)\; =\; 12\backslash left(1-\backslash left(\backslash frac\backslash right)\backslash right)h(D).$

Prime-count related

Let $H\_n\; =\; 1\; +\; \backslash frac12\; +\; \backslash frac13\; +\; \backslash cdots\; +\backslash frac$ be the ''n''th harmonic number. Then :$\backslash sigma(n)\; \backslash le\; H\_n\; +\; e^\backslash log\; H\_n$ is true for every natural number ''n'' if and only if the Riemann hypothesis is true. The Riemann hypothesis is also equivalent to the statement that, for all ''n'' > 5040, :$\backslash sigma(n)\; <\; e^\backslash gamma\; n\; \backslash log\; \backslash log\; n$ (where γ is the Euler–Mascheroni constant). This is Robin's theorem. :$\backslash sum\_\backslash nu\_p(n)\; =\; \backslash Omega(n).$ :$\backslash psi(x)=\backslash sum\_\backslash Lambda(n).$ :$\backslash Pi(x)=\; \backslash sum\_\backslash frac.$ :$e^=\backslash prod\_p.$ :$e^=\; \backslash operatorname,2,\backslash dots,\backslash lfloor\; x\backslash rfloor$

Menon's identity

In 1965 P Kesava Menon proved :$\backslash sum\_\; \backslash gcd(k-1,n)\; =\backslash varphi(n)d(n).$ This has been generalized by a number of mathematicians. For example, B. Sury :$\backslash sum\_\; \backslash gcd(k\_1-1,k\_2,\backslash dots,k\_s,n)\; =\backslash varphi(n)\backslash sigma\_(n).$ N. Rao :$\backslash sum\_\; \backslash gcd(k\_1-a\_1,k\_2-a\_2,\backslash dots,k\_s-a\_s,n)^s\; =J\_s(n)d(n),$ where ''a''_{1}, ''a''_{2}, ..., ''a''_{''s''} are integers, gcd(''a''_{1}, ''a''_{2}, ..., ''a''_{''s''}, ''n'') = 1.
László Fejes Tóth
:$\backslash sum\_\; \backslash gcd(k^2-1,m\_1)\backslash gcd(k^2-1,m\_2)\; =\backslash varphi(n)\backslash sum\_\; \backslash varphi(\backslash gcd(d\_1,\; d\_2))2^,$
where ''m''_{1} and ''m''_{2} are odd, ''m'' = lcm(''m''_{1}, ''m''_{2}).
In fact, if ''f'' is any arithmetical function
:$\backslash sum\_\; f(\backslash gcd(k-1,n))\; =\backslash varphi(n)\backslash sum\_\backslash frac,$
where * stands for Dirichlet convolution.

Miscellaneous

Let ''m'' and ''n'' be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity: :$\backslash left(\backslash frac\backslash right)\; \backslash left(\backslash frac\backslash right)\; =\; (-1)^.$ Let ''D''(''n'') be the arithmetic derivative. Then the logarithmic derivative : $\backslash frac\; =\; \backslash sum\_\; \backslash frac$ 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 textn=\backslash begin1,2,\; 4;\backslash \backslash \; 3,5,7,9,11,\; \backslash ldots\; \backslash text\; p^k\; \backslash textp\backslash text;\backslash \backslash \; 6,10,14,18,\backslash ldots\; \backslash text\; 2p^k\backslash textp\backslash text.\; \backslash end$ See Multiplicative group of integers modulo n and Primitive root modulo n. :$2^\; \backslash le\; d(n)\; \backslash le\; 2^.$ :$\backslash frac<\backslash frac\; <\; 1.$ :$\backslash begin\; c\_q(n)\; \&=\backslash frac\backslash phi(q)\backslash \backslash \; \&=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta.\; \backslash end$ Note that $\backslash phi(q)\; =\; \backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta.$ :$c\_q(1)\; =\; \backslash mu(q).$ :$c\_q(q)\; =\; \backslash phi(q).$ :$\backslash sum\_d^(\backslash delta)\; =\; \backslash left(\backslash sum\_d(\backslash delta)\backslash right)^2.$ Compare this with 1^{3} + 2^{3} + 3^{3} + ... + ''n''^{3} = (1 + 2 + 3 + ... + ''n'')^{2}
:$d(uv)\; =\; \backslash sum\_\backslash mu(\backslash delta)d\backslash left(\backslash frac\backslash right)d\backslash left(\backslash frac\backslash right).$
:$\backslash sigma\_k(u)\backslash sigma\_k(v)\; =\; \backslash sum\_\backslash delta^k\backslash sigma\_k\backslash left(\backslash frac\backslash right).$
:$\backslash tau(u)\backslash tau(v)\; =\; \backslash sum\_\backslash delta^\backslash tau\backslash left(\backslash frac\backslash right),$ where ''τ''(''n'') is Ramanujan's function. Apostol, ''Modular Functions ...'', ch. 6 eq. 3

** First 100 values of some arithmetic functions **

Notes

** References **

*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

Further reading

*

External links

* * Matthew Holden, Michael Orrison, Michael Varbl

Yet another Generalization of Euler's Totient Function

* Huard, Ou, Spearman, and Williams

Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions

* Dineva, Rosica

The Euler Totient, the Möbius, and the Divisor Functions

* László Tóth

Menon's Identity and arithmetical sums representing functions of several variables

{{Authority control Category:Functions and mappings

Multiplicative and additive 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''(''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''(''mn'') = ''a''(''m'')''a''(''n'') for all coprime natural numbers ''m'' and ''n''.

Notation

$\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$ :$\backslash prod\_p\; f(p)=\; f(2)f(3)f(5)\backslash cdots.$ Similarly, $\backslash sum\_\; f(p^k)$ and $\backslash prod\_\; f(p^k)$ mean that the sum or product is over all prime powers with strictly positive exponent (so ''k'' = 0 is not included): :$\backslash sum\_\; f(p^k)\; =\; \backslash sum\_p\backslash sum\_\; f(p^k)\; =\; f(2)\; +\; f(3)\; +\; f(4)\; +f(5)\; +f(7)+f(8)+f(9)+\backslash cdots$ $\backslash sum\_\; f(d)$ and $\backslash prod\_\; f(d)$ mean that the sum or product is over all positive divisors of ''n'', including 1 and ''n''. For example, if ''n'' = 12, :$\backslash prod\_\; f(d)\; =\; f(1)f(2)\; f(3)\; f(4)\; f(6)\; f(12).\backslash $ The notations can be combined: $\backslash sum\_\; f(p)$ and $\backslash prod\_\; f(p)$ mean that the sum or product is over all prime divisors of ''n''. For example, if ''n'' = 18, :$\backslash sum\_\; f(p)\; =\; f(2)\; +\; f(3),\backslash $ and similarly $\backslash sum\_\; f(p^k)$ and $\backslash prod\_\; f(p^k)$ mean that the sum or product is over all prime powers dividing ''n''. For example, if ''n'' = 24, :$\backslash prod\_\; f(p^k)\; =\; f(2)\; f(3)\; f(4)\; f(8).\backslash $

Ω(''n''), ''ω''(''n''), ''ν''

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^\backslash cdots\; p\_k^$ where ''p''

Multiplicative functions

σ

σ

φ(''n'') – Euler totient function

φ(''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\_\; \backslash left(1-\backslash frac\backslash right)\; =n\; \backslash left(\backslash frac\backslash right)\backslash left(\backslash frac\backslash right)\; \backslash cdots\; \backslash left(\backslash frac\backslash right)\; .$

J

J

μ(''n'') – Möbius function

μ(''n''), the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below. :$\backslash mu(n)=\backslash begin\; (-1)^=(-1)^\; \&\backslash text\backslash ;\; \backslash omega(n)\; =\; \backslash Omega(n)\backslash \backslash \; 0\&\backslash text\backslash ;\backslash omega(n)\; \backslash ne\; \backslash Omega(n).\backslash end$ This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(''n'') – Ramanujan tau function

τ(''n''), the Ramanujan tau function, is defined by its generating function identity: :$\backslash sum\_\backslash tau(n)q^n=q\backslash prod\_(1-q^n)^.$ Although it is hard to say exactly what "arithmetical property of ''n''" it "expresses", (''τ''(''n'') is (2π)

''c''

''c''

''ψ''(''n'') - Dedekind psi function

The Dedekind psi function, used in the theory of modular functions, is defined by the formula :$\backslash psi(n)\; =\; n\; \backslash prod\_\backslash left(1+\backslash frac\backslash right).$

Completely multiplicative functions

λ(''n'') – Liouville function

''λ''(''n''), the Liouville function, is defined by :$\backslash lambda\; (n)\; =\; (-1)^.$

''χ''(''n'') – characters

All Dirichlet characters ''χ''(''n'') are completely multiplicative. Two characters have special notations: The principal character (mod ''n'') is denoted by ''χ''

Additive functions

''ω''(''n'') – distinct prime divisors

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

Completely additive functions

Ω(''n'') – prime divisors

Ω(''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'', ''ν''

Neither multiplicative nor additive

(''x''), Π(''x''), ''θ''(''x''), ''ψ''(''x'') – prime count functions

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\_1$ A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ... It is the summation function of the arithmetic function which takes the value 1/''k'' on integers which are the k-th power of some prime number, and the value 0 on other integers. :$\backslash Pi(x)\; =\; \backslash sum\_\backslash frac.$ ''θ''(''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\_\; \backslash log\; p,$ :$\backslash psi(x)\; =\; \backslash sum\_\; \backslash log\; p.$ The Chebyshev function ''ψ''(''x'') is the summation function of the von Mangoldt function just below.

Λ(''n'') – von Mangoldt function

Λ(''n''), the von Mangoldt function, is 0 unless the argument ''n'' is a prime power , in which case it is the natural log of the prime ''p'': :$\backslash Lambda(n)\; =\; \backslash begin\backslash log\; p\; \&\backslash text\; n\; =\; 2,3,4,5,7,8,9,11,13,16,\backslash ldots=p^k\; \backslash text\backslash \backslash \; 0\&\backslash text\; n=1,6,10,12,14,15,18,20,21,\backslash dots\; \backslash ;\backslash ;\backslash ;\backslash ;\backslash text.\; \backslash end$

''p''(''n'') – partition function

''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: :$p(n)\; =\; |\backslash left\backslash |.$

λ(''n'') – Carmichael function

''λ''(''n''), the Carmichael function, is the smallest positive number such that $a^\backslash equiv\; 1\; \backslash pmod$ 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\; \backslash ;\backslash ;\backslash phi(n)\; \&\backslash textn\; =\; 2,3,4,5,7,9,11,13,17,19,23,25,27,\backslash dots\backslash \backslash \; \backslash tfrac12\backslash phi(n)\&\backslash textn=8,16,32,64,\backslash dots\; \backslash end$ and for general ''n'' it is the least common multiple of λ of each of the prime power factors of ''n'': :$\backslash lambda(p\_1^p\_2^\; \backslash dots\; p\_^)\; =\; \backslash operatornamelambda(p\_1^),\backslash ;\backslash lambda(p\_2^),\backslash dots,\backslash lambda(p\_^)$

''h''(''n'') – Class number

''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''

''r''

''D''(''n'') – Arithmetic derivative

Using the Heaviside notation for the derivative, ''D''(''n'') is a function such that : $D(n)\; =\; 1$ if ''n'' prime, and : $D(mn)\; =\; m\; D(n)\; +\; D(m)\; n$ (Product rule)

Dirichlet convolution

Given an arithmetic function ''a''(''n''), let ''F''

Relations among the functions

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:

Dirichlet convolutions

:$\backslash sum\_\backslash mu(\backslash delta)=\; \backslash sum\_\backslash lambda\backslash left(\backslash frac\backslash right)|\backslash mu(\backslash delta)|=\; \backslash begin\; 1\; \&\; \backslash text\; n=1\backslash \backslash \; 0\; \&\; \backslash text\; n\backslash ne1\; \backslash end$ where ''λ'' is the Liouville function. :$\backslash sum\_\backslash varphi(\backslash delta)\; =\; n.$ ::$\backslash varphi(n)\; =\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta\; =n\backslash sum\_\backslash frac.$ Möbius inversion :$\backslash sum\_\; J\_k(d)\; =\; n^k.$ ::$J\_k(n)\; =\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta^k\; =n^k\backslash sum\_\backslash frac.$ Möbius inversion :$\backslash sum\_\backslash delta^sJ\_r(\backslash delta)J\_s\backslash left(\backslash frac\backslash right)\; =\; J\_(n)$ :$\backslash sum\_\backslash varphi(\backslash delta)d\backslash left(\backslash frac\backslash right)=\; \backslash sigma(n).$ :$\backslash sum\_|\backslash mu(\backslash delta)|=\; 2^.$ ::$|\backslash mu(n)|=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)2^.$ Möbius inversion :$\backslash sum\_2^=\; d(n^2).$ ::$2^=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)d(\backslash delta^2).$ Möbius inversion :$\backslash sum\_d(\backslash delta^2)=\; d^2(n).$ ::$d(n^2)=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)d^2(\backslash delta).$ Möbius inversion :$\backslash sum\_d\backslash left(\backslash frac\backslash right)2^=\; d^2(n).$ :$\backslash sum\_\backslash lambda(\backslash delta)=\backslash begin\; \&1\backslash text\; n\; \backslash text\backslash \backslash \; \&0\backslash text\; n\; \backslash text\; \backslash end$ where λ is the Liouville function. :$\backslash sum\_\backslash Lambda(\backslash delta)\; =\; \backslash log\; n.$ ::$\backslash Lambda(n)=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash log(\backslash delta).$ Möbius inversion

Sums of squares

For all $k\; \backslash ge\; 4,\backslash ;\backslash ;\backslash ;\; r\_k(n)\; >\; 0.$ (Lagrange's four-square theorem). : :$r\_2(n)\; =\; 4\backslash sum\_\backslash left(\backslash frac\backslash right),$ where the Kronecker symbol has the values :$\backslash left(\backslash frac\backslash right)\; =\; \backslash begin\; +1\&\backslash textn\backslash equiv\; 1\; \backslash pmod\; 4\; \backslash \backslash \; -1\&\backslash textn\backslash equiv\; 3\; \backslash pmod\; 4\backslash \backslash \; \backslash ;\backslash ;\backslash ;0\&\backslash textn\backslash text.\backslash \backslash \; \backslash end$ There is a formula for r

Divisor sum convolutions

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\_^\backslash infty\; a\_n\; x^n\backslash right)\backslash left(\backslash sum\_^\backslash infty\; b\_n\; x^n\backslash right)\; =\; \backslash sum\_^\backslash infty\; \backslash sum\_^\backslash infty\; a\_i\; b\_j\; x^\; =\; \backslash sum\_^\backslash infty\; \backslash left(\backslash sum\_^n\; a\_i\; b\_\backslash right)\; x^n\; =\; \backslash sum\_^\backslash infty\; c\_n\; x^n\; .$ The sequence $c\_n\; =\; \backslash sum\_^n\; a\_i\; b\_$ is called the convolution or the Cauchy product of the sequences ''a''

These formulas may be proved analytically (see Eisenstein series) or by elementary methods. :$\backslash sigma\_3(n)\; =\; \backslash frac\backslash left\backslash .$ Ramanujan, ''On Certain Arithmetical Functions'', Table IV; ''Papers'', p. 146 :$\backslash sigma\_5(n)\; =\; \backslash frac\backslash left\backslash .$ Koblitz, ex. III.2.8 :$\backslash begin\; \backslash sigma\_7(n)\; \&=\backslash frac\backslash left\backslash \backslash \backslash \; \&=\backslash sigma\_3(n)\; +\; 120\backslash sum\_\backslash sigma\_3(k)\backslash sigma\_3(n-k).\; \backslash end$ :$\backslash begin\; \backslash sigma\_9(n)\; \&=\; \backslash frac\backslash left\backslash \backslash \backslash \; \&=\; \backslash frac\backslash left\backslash .\; \backslash end$ :$\backslash tau(n)\; =\; \backslash frac\backslash sigma\_(n)\; +\; \backslash frac\backslash sigma\_(n)\; -\; \backslash frac\backslash sum\_\backslash sigma\_5(k)\backslash sigma\_5(n-k),$ where ''τ''(''n'') is Ramanujan's function. Since ''σ''

Class number related

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number ''h'' of quadratic number fields to the Jacobi symbol. 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). Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol: :$\backslash left(\backslash frac\backslash right)\; =\; \backslash begin\; \backslash ;\backslash ;\backslash ,0\&\backslash text\; a\; \backslash text\; \backslash \backslash (-1)^\&\backslash texta\; \backslash text\; \backslash end$ Then if ''D'' < −4 is a fundamental discriminant :$\backslash begin\; h(D)\; \&\; =\; \backslash frac\; \backslash sum\_^r\backslash left(\backslash frac\backslash right)\backslash \backslash \; \&\; =\; \backslash frac\; \backslash sum\_^\backslash left(\backslash frac\backslash right).\; \backslash end$ There is also a formula relating ''r''

Prime-count related

Let $H\_n\; =\; 1\; +\; \backslash frac12\; +\; \backslash frac13\; +\; \backslash cdots\; +\backslash frac$ be the ''n''th harmonic number. Then :$\backslash sigma(n)\; \backslash le\; H\_n\; +\; e^\backslash log\; H\_n$ is true for every natural number ''n'' if and only if the Riemann hypothesis is true. The Riemann hypothesis is also equivalent to the statement that, for all ''n'' > 5040, :$\backslash sigma(n)\; <\; e^\backslash gamma\; n\; \backslash log\; \backslash log\; n$ (where γ is the Euler–Mascheroni constant). This is Robin's theorem. :$\backslash sum\_\backslash nu\_p(n)\; =\; \backslash Omega(n).$ :$\backslash psi(x)=\backslash sum\_\backslash Lambda(n).$ :$\backslash Pi(x)=\; \backslash sum\_\backslash frac.$ :$e^=\backslash prod\_p.$ :$e^=\; \backslash operatorname,2,\backslash dots,\backslash lfloor\; x\backslash rfloor$

Menon's identity

In 1965 P Kesava Menon proved :$\backslash sum\_\; \backslash gcd(k-1,n)\; =\backslash varphi(n)d(n).$ This has been generalized by a number of mathematicians. For example, B. Sury :$\backslash sum\_\; \backslash gcd(k\_1-1,k\_2,\backslash dots,k\_s,n)\; =\backslash varphi(n)\backslash sigma\_(n).$ N. Rao :$\backslash sum\_\; \backslash gcd(k\_1-a\_1,k\_2-a\_2,\backslash dots,k\_s-a\_s,n)^s\; =J\_s(n)d(n),$ where ''a''

Miscellaneous

Let ''m'' and ''n'' be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity: :$\backslash left(\backslash frac\backslash right)\; \backslash left(\backslash frac\backslash right)\; =\; (-1)^.$ Let ''D''(''n'') be the arithmetic derivative. Then the logarithmic derivative : $\backslash frac\; =\; \backslash sum\_\; \backslash frac$ 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 textn=\backslash begin1,2,\; 4;\backslash \backslash \; 3,5,7,9,11,\; \backslash ldots\; \backslash text\; p^k\; \backslash textp\backslash text;\backslash \backslash \; 6,10,14,18,\backslash ldots\; \backslash text\; 2p^k\backslash textp\backslash text.\; \backslash end$ See Multiplicative group of integers modulo n and Primitive root modulo n. :$2^\; \backslash le\; d(n)\; \backslash le\; 2^.$ :$\backslash frac<\backslash frac\; <\; 1.$ :$\backslash begin\; c\_q(n)\; \&=\backslash frac\backslash phi(q)\backslash \backslash \; \&=\backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta.\; \backslash end$ Note that $\backslash phi(q)\; =\; \backslash sum\_\backslash mu\backslash left(\backslash frac\backslash right)\backslash delta.$ :$c\_q(1)\; =\; \backslash mu(q).$ :$c\_q(q)\; =\; \backslash phi(q).$ :$\backslash sum\_d^(\backslash delta)\; =\; \backslash left(\backslash sum\_d(\backslash delta)\backslash right)^2.$ Compare this with 1

Notes

Further reading

*

External links

* * Matthew Holden, Michael Orrison, Michael Varbl

Yet another Generalization of Euler's Totient Function

* Huard, Ou, Spearman, and Williams

Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions

* Dineva, Rosica

The Euler Totient, the Möbius, and the Divisor Functions

* László Tóth

Menon's Identity and arithmetical sums representing functions of several variables

{{Authority control Category:Functions and mappings