Difference between revisions of "Euler totient function"
(→Behavior) |
|||
Line 22: | Line 22: | ||
<math>\frac{\varphi(n)}{n} = \prod_{i=1}^r \left(1 - \frac{1}{p_i} \right)</math>. | <math>\frac{\varphi(n)}{n} = \prod_{i=1}^r \left(1 - \frac{1}{p_i} \right)</math>. | ||
− | == | + | ==Properties== |
− | === | + | {| class="sortable" border="1" |
+ | ! Property !! Satisfied? !! Statement with symbols | ||
+ | |- | ||
+ | | [[satisfies property::multiplicative function]] || Yes || If <math>m</math> and <math>n</math> are relatively prime [[natural number]]s, then <math>\varphi(mn) = \varphi(m)\varphi(n)</math>. | ||
+ | |- | ||
+ | | [[dissatisfies property::completely multiplicative function]] || No || It is not true for arbitrary natural numbers <math>m</math> and <math>n</math> that <math>\varphi(mn) = \varphi(m)\varphi(n)</math>. For instance, if <math>m = n = 2</math>, then <math>\varphi(m) = \varphi(n) = 1</math> whereas <math>\varphi(mn)</math> is 2. | ||
+ | |- | ||
+ | | [[satisfies property::divisibility-preserving function]] || Yes || If <math>m</math> and <math>n</math> are natural numbers such that <math>m</math>divides <math>n</math>, then <math>\varphi(m)</math> divides <math>\varphi(n)</math>. | ||
+ | |} | ||
− | + | ==Behavior== | |
− | + | ===High and low points (relatively speaking)=== | |
− | <math>\ | + | * '''Primes are high points''': We also have <math>\varphi(n) \le n - 1</math> for <matH>n > 1</math>. Equality occurs if and only if <math>n</math> is a [[prime number]]. |
+ | * '''Primorials are low points''': Roughly, the numbers occurring as [[primorial]]s (products of the first few primes) have the lowest value of <math>\varphi(n)</math> relative to <math>n</math>, compared with other similarly sized numbers. | ||
− | === | + | ===Measures of difference=== |
− | + | We use the [[infinitude of primes]] for arguing about limit superiors. | |
− | <math>\varphi(n) | + | {| class="sortable" border="1" |
− | + | ! Measure !! Limit superior !! Explanation !! Limit inferior !! Explanation | |
− | + | |- | |
− | + | | <math>\varphi(n) - n</math> || -1 || maximum value of -1 occurs at primes || <math>-\infty</math> || Consider the sequence of powers 2. <math>\varphi(2^k) = 2^{k-1}</math>, so <math>\varphi(2^k) - 2^k = -2^{k-1} \to -\infty</math>. | |
− | <math>\varphi(n) \ge n^{1 - | + | |- |
+ | | <math>\frac{\varphi(n)}{n}</math> || 1 || At each prime <math>p</math>, value is <math>1 - (1/p)</math>. Limit is 1 as <math>p \to \infty</math> || 0 || Consider the sequence of primorials. The corresponding values of <math>\varphi(n)/n</math> are products of the values <math>1 - (1/p)</math> for the first few primes <math>p</math>. The limit of these is the infinite product <math>\prod_p \left(1 - \frac{1}{p}\right)</math> over all prime <math>p</math>. This diverges because the infinite sum of the reciprocals of the primes diverges. | ||
+ | |- | ||
+ | | <math>\frac{\ln \varphi(n)}{\ln n}</math> || 1 || For each prime <math>p</math>, the limit is <math>\ln(p - 1)/\ln p</math> ,which approaches 1. || 1 || We can show that for every <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that <math>\varphi(n) \ge n^{1 - \varepsilon}</math> for all <math>n \ge N_\varepsilon</math>. | ||
+ | |} | ||
==Summatory function and average value== | ==Summatory function and average value== | ||
Line 81: | Line 94: | ||
* [[Polygonal number]]: A natural number <math>n</math> such that <math>\varphi(n)</math> is a power of <math>2</math>, or equivalently, such that the regular <math>n</math>-gon is constructible using straightedge and compass. | * [[Polygonal number]]: A natural number <math>n</math> such that <math>\varphi(n)</math> is a power of <math>2</math>, or equivalently, such that the regular <math>n</math>-gon is constructible using straightedge and compass. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Dirichlet series== | ==Dirichlet series== |
Revision as of 22:03, 29 January 2014
This article defines an arithmetic function or number-theoretic function: a function from the natural numbers to a ring (usually, the ring of integers, rational numbers, real numbers, or complex numbers).
View a complete list of arithmetic functions
Contents
Definition
Let be a natural number. The Euler phi-function or Euler totient function of , denoted , is defined as following:
- It is the order of the multiplicative group modulo , i.e., the multiplicative group of the ring of integers modulo .
- It is the number of elements in that are relatively prime to .
In terms of prime factorization
Suppose we have the following prime factorization of :
.
Then, we have:
.
In other words:
.
Properties
Property | Satisfied? | Statement with symbols |
---|---|---|
multiplicative function | Yes | If and are relatively prime natural numbers, then . |
completely multiplicative function | No | It is not true for arbitrary natural numbers and that . For instance, if , then whereas is 2. |
divisibility-preserving function | Yes | If and are natural numbers such that divides , then divides . |
Behavior
High and low points (relatively speaking)
- Primes are high points: We also have for . Equality occurs if and only if is a prime number.
- Primorials are low points: Roughly, the numbers occurring as primorials (products of the first few primes) have the lowest value of relative to , compared with other similarly sized numbers.
Measures of difference
We use the infinitude of primes for arguing about limit superiors.
Measure | Limit superior | Explanation | Limit inferior | Explanation |
---|---|---|---|---|
-1 | maximum value of -1 occurs at primes | Consider the sequence of powers 2. , so . | ||
1 | At each prime , value is . Limit is 1 as | 0 | Consider the sequence of primorials. The corresponding values of are products of the values for the first few primes . The limit of these is the infinite product over all prime . This diverges because the infinite sum of the reciprocals of the primes diverges. | |
1 | For each prime , the limit is ,which approaches 1. | 1 | We can show that for every , there exists such that for all . |
Summatory function and average value
Summatory function
The summatory function of the Euler phi-function is termed the totient summatory function.
Relation with other arithmetic functions
Similar functions
- Universal exponent (also called Carmichael function) is the exponent of the multiplicative group modulo . The universal exponent of , usually denoted , divides .
- Dedekind psi-function is similar tothe Euler phi-function, and is defined as:
.
Relations expressed in terms of Dirichlet products
- : In other words, the Dirichlet product of the Euler phi-function and the all ones function is the identity function:
.
- : This is obtained by applying the Mobius inversion formula to the previous identity. The Euler phi-function is thus the Dirichlet product of the identity function and the Mobius function:
.
- : In other words, the Dirichlet product of the Euler phi-function and the divisor count function equals the divisor sum function:
.
- .
Inequalities
- : Here, is the prime-counting function, and counts the number of primes less than or equal to , while is the prime divisor count function of .
- : Here, is the divisor count function, counting the total number of divisors of .
Relation with properties of numbers
- Prime number: A natural number such that .
- Polygonal number: A natural number such that is a power of , or equivalently, such that the regular -gon is constructible using straightedge and compass.
Dirichlet series
Further information: Formula for Dirichlet series of Euler phi-function
The Dirichlet series for the Euler phi-function is given by:
.
Using the Dirichlet product identity and the fact that Dirichlet series of Dirichlet product equals product of Dirichlet series, we get:
.
This simplifies to:
.
This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions.
Algebraic significance
The Euler phi-function of is important in the following ways:
- It is the number of generators of the cyclic group of order .
- It is the order of the multiplicative group of the ring of integers modulo (in fact, this multiplicative group is precisely the set of generators of the additive group).