In number theory, an arithmetic, arithmetical, or number-theoretic function[1][2] is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers.
mean that the sum or product is over all prime powers with strictly positive exponent (so k = 0 is not included):
mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if n = 12, then
mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then
The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes:
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.
In terms of the above the prime omega functions ω and Ω are defined by To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms of n and the corresponding pi, ai, ω, 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.
σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).
φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.
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) = J1(n).
Although it is hard to say exactly what "arithmetical property of n" it "expresses",[7] (τ(n) is (2π)−12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function)[8] 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).
Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer.
The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n):
is the Legendre symbol, defined for all integers a and all odd primes p by
For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.
π(x), the prime-counting function, is the number of primes not exceeding x.
ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x.
λ(n), the Carmichael function, is the smallest positive number such that
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:
and for general n it is the least common multiple of λ of each of the prime power factors of 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.
rk(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.
Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples.
In some cases it may be possible to find asymptotic behaviour for the summation function for large x.
where the Kronecker symbol has the values There is a formula for r3 in the section on class numbers below.
That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, that is, σ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. Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.
is called the convolution or the Cauchy product of the sequences an and bn.
These formulas may be proved analytically (see Eisenstein series) or by elementary methods.
[28] Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences[35] for the functions.
Then the Jacobi symbol satisfies the law of quadratic reciprocity: