Added to Favorites

Related Searches

Definitions

In number theory an arithmetic function or arithmetical function is a function defined on the set of natural numbers (i.e. positive integers) that takes real or complex values. A simple example of an arithmetic function is the characteristic function of even positive integers, which takes the value 0 at the odd integers 1,3,5,7... and the value 1 at the even integers 2,4,6,8...## Multiplicative and additive functions

## Examples

## Prime power decomposition

_{i} is prime and each a_{j} ≥ 1. For example 10 = 2^{1}.5^{1}, 25 = 5^{2}, 666 = 2^{1}.3^{2}.37^{1}, etc.## Summation functions

_{P}(n).## Convolution

_{a}(s) is called a generating function of a(n). One key example is given by a(n) = 1 for all n. In this case F_{a}(s) = ς(s), the Riemann zeta function._{a}(s)F_{b}(s) = F_{c}(s) where c is some arithmetic function given by
## References

To emphasise that they are functions, values of an arithmetic function are usually denoted by a(n) rather than a_{n}. A large part of number theory consists of the study of these functions.

Let (m,n) denote the greatest common divisor of m and n. An arithmetic function a is said to be

- multiplicative if a(mn) = a(m)a(n) for all natual numbers m and n such that (m,n) = 1;
- completely multiplicative if a(mn) = a(m)a(n) for all natural numbers m and n;
- additive if a(mn) = a(m)+a(n) for all natual numbers m and n such that (m,n) = 1;
- completely additive if a(mn) = a(m)+a(n) for all natural numbers m and n.

- π(n), the prime counting function - the number of primes less than or equal to n. This arithmetic function is neither multiplicative nor additive, e.g. π(7) = 4 and π(11) = 5, but π(7×11) = π(77) = 21 ≠ 4×5.
- τ(n), the number of positive divisors of n, including 1 and n. This arithmetic function is multiplicative.
- ω(n), the number of distinct primes dividing the number n. This arithmetic function is additive.
- Ω(n), the number of prime factors of n, counted with multiplicities. This arithmetic function is completely additive.
- λ(n), the Liouville function - defined by λ(n) := (-1)
^{Ω(n)}. This arithmetic function is completely multiplicative (by the last example). - Λ(n), the von Mangoldt function - defined to be ln(p) if n is an integer power of a prime p and 0 for all other n. This arithmetic function is neither multiplicative nor additive, e.g. Λ(2) = ln(2), Λ(3) = ln(3), but Λ(2×3) = 0 ≠ ln(2)×ln(3).
- P(n), the partition function - the number of unordered representations of n as a sum of positive integers; neither multiplicative nor additive.
- χ(n) - defined by the following

- $chi(n)\; :=\; left\{begin\{array\}\{cl\}\; 0\; \&\; mbox\{if\; \}\; n\; mbox\{\; is\; even\},\; 1\; \&\; mbox\{if\; \}\; n\; equiv\; 1\; mod\; 4,\; -1\; \&\; mbox\{if\; \}\; n\; equiv\; 3\; mod\; 4.$

- This arithmetic function is completely multiplicative.

- μ(n), the Möbius function - defined as follows: μ(1) := 1, and

- $mu(n)\; :=\; left\{begin\{array\}\{cl\}\; (-1)^k\; \&\; mbox\{if\; \}\; n\; mbox\{\; is\; a\; product\; of\; \}\; k\; mbox\{\; distinct\; primes\}$

- The definition of the Möbius function presents itself naturally when working with Euler products. This arithmetic function is multiplicative.

Some of the arithmetic functions above can be computed easily using prime power decomposition. Any positive integer n can be factorised uniquely as a product of powers of primes, as follows:

- $n\; =\; p\_1^\{a\_1\}ldots\; p\_k^\{a\_k\}$

Arithmetic functions can then be defined as follows:

- τ(n) = (1 + a
_{1})...(1 + a_{k}) - ω(n) = k
- Ω(n) = a
_{1}+ ... + a_{k} - Λ(n) = ln(p
_{1}) if k = 1; otherwise Λ(n) = 0. - μ(n) = 0 if a
_{i}> 1 for any i; otherwise μ(n) = (-1)^{k}.

An exact expression for π(n) in terms of the k, the p_{i} and the a_{j} is so far not known. The prime number theorem gives an estimate for π(n) as n becomes very large. Certain remainer terms to improve the prime number theorem have been postulated, and these are linked to the Reimann hypothesis.

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

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

Given any set E of the natural numbers (for example, the set of prime numbers), define

- $u\_E(n)\; :=\; left\{\; begin\{array\}\{ll\}\; 1\; \&\; mbox\{if\}\; n\; in\; E$

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. The prime number theorem gives asymptotic behaviour for π(x) (the summation function of u_{P}(n)) for large x.

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)\; :=\; sum\_\{n=1\}^\{infty\}\; frac\{a(n)\}\{n^s\}\; .$

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)\; =\; left(sum\_\{m=1\}^\{infty\}frac\{a(m)\}\{m^s\}\; right)left(sum\_\{n=1\}^\{infty\}frac\{b(n)\}\{n^s\}\; right)\; .$

- $c(n)\; :=\; sum\_\{ij\; =\; n\}\; a(i)b(j)\; =\; sum\_\{i|n\}a(i)bleft(frac\{n\}\{i\}right)\; ,$

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 09:27:49 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 09:27:49 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.