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
In this article, and mean that the sum or product is over all prime numbers:
and
Similarly, and mean that the sum or product is over all prime powers with strictly positive exponent (so is not included):
The notations and mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if , then
The notations can be combined: and mean that the sum or product is over all prime divisors of n. For example, if n = 18, then
and similarly and mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then
Ω(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: where p1 < p2 < ... < pk are primes and the aj 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 pi then νp(n) = ai, otherwise it is zero. Then
In terms of the above the prime omega functions ω and Ω are defined by
To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω.
Multiplicative functions
σk(n), τ(n), d(n) – divisor sums
σ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.
σ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).
Setting k = 0 in the second product gives
φ(n) – Euler totient function
φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.
Jk(n) – Jordan totient function
Jk(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, .
μ(n) – Möbius function
μ(n), the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below.
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:
Although it is hard to say exactly what "arithmetical property of n" it "expresses", (τ(n) is (2π)−12 times the nth 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 rk(n) functions (because these are also coefficients in the expansion of modular forms).
cq(n) – Ramanujan's sum
cq(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity: