Difference between revisions of "Euler totient function"

From Number
Jump to: navigation, search
(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>.
  
==Behavior==
+
==Properties==
  
===Upper bound===
+
{| 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>.
 +
|}
  
The largest values of <math>\varphi(n)</math> (relative to <math>n</math>) are taken when <math>n</math> is prime. <math>\varphi(p) = p - 1</math> for a prime <math>p</math>.
+
==Behavior==
  
Thus, due to the [[infinitude of primes]], we obtain that:
+
===High and low points (relatively speaking)===
  
<math>\lim \sup_{n \to \infty} \frac{\varphi(n)}{n} = 1</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.
  
===Lower bound===
+
===Measures of difference===
  
For any <math>\varepsilon > 0</math>, there exists <math>N_\varepsilon</math> such that:
+
We use the [[infinitude of primes]] for arguing about limit superiors.
  
<math>\varphi(n) \ge n^{1 - \varepsilon} \ \forall \ n \ge N_\varepsilon</math>.
+
{| class="sortable" border="1"
 
+
! Measure !! Limit superior !! Explanation !! Limit inferior !! Explanation
With the [[prime number theorem]], we can find a constant <math>C</math> such that:
+
|-
 
+
| <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 - (C\log\log n/\log n)}</math>.
+
|-
 +
| <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.
  
==Properties==
 
 
{{multiplicative}}
 
 
{{not completely multiplicative}}
 
 
{{divisibility-preserving}}
 
  
If <math>m</math> divides <math>n</math>, then <math>\varphi(m)</math> divides <math>\varphi(n)</math>.
 
  
 
==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

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

.

.

.

  • .

Inequalities

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).