Arithmetic function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (→Examples: added lambda function) |
imported>Jitse Niesen (remove "See also" section because it is subsumed in the "Related Articles" subpage; perhaps the "Examples" section should go for the same reason, though it may be better to flesh it out a bit) |
||
| (4 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In [[number theory]], an '''arithmetic function''' is a function defined on the set of [[ | In [[number theory]], an '''arithmetic function''' is a function defined on the set of [[positive integer]]s, usually with [[integer]], [[real number|real]] or [[complex number|complex]] values. | ||
==Classes of arithmetic function== | ==Classes of arithmetic function== | ||
Arithmetic functions which have some connexion with the additive or multiplicative structure of the integers are of particular interest in number theory. | Arithmetic functions which have some connexion with the additive or multiplicative structure of the integers are of particular interest in number theory. | ||
===Multiplicative functions=== | |||
We define a function ''a''(''n'') on positive integers to be | |||
* '''Totally multiplicative''' if <math>a(mn) = a(m) a(n)</math> for all ''m'' and ''n''. | * '''Totally multiplicative''' if <math>a(mn) = a(m) a(n)</math> for all ''m'' and ''n''. | ||
* '''Multiplicative''' if <math>a(mn) = a(m) a(n)</math> whenever ''m'' and ''n'' are [[coprime]]. | * '''Multiplicative''' if <math>a(mn) = a(m) a(n)</math> whenever ''m'' and ''n'' are [[coprime]]. | ||
The ''[[Dirichlet convolution]]'' of two arithmetic function ''a''(''n'') and ''b''(''n'') is defined as | |||
:<math>a \star b (n) = \sum_{d \mid n} a(d) b(n/d) .\,</math> | |||
If ''a'' and ''b'' are multiplicative, so is their convolution. | |||
==Examples== | ==Examples== | ||
* Carmichael's [[lambda function]] | * Carmichael's [[lambda function]] | ||
* A [[Dirichlet character]] | |||
* [[Euler]]'s [[totient function]] | * [[Euler]]'s [[totient function]] | ||
* [[Jordan's totient function]] | * [[Jordan's totient function]] | ||
* [[Möbius function]] | |||
* [[ | |||
Latest revision as of 06:03, 15 June 2009
In number theory, an arithmetic function is a function defined on the set of positive integers, usually with integer, real or complex values.
Classes of arithmetic function
Arithmetic functions which have some connexion with the additive or multiplicative structure of the integers are of particular interest in number theory.
Multiplicative functions
We define a function a(n) on positive integers to be
- Totally multiplicative if for all m and n.
- Multiplicative if whenever m and n are coprime.
The Dirichlet convolution of two arithmetic function a(n) and b(n) is defined as
If a and b are multiplicative, so is their convolution.