Euler totient function: Difference between revisions

Revision as of 01:39, 29 April 2009

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 $n$ be a natural number. The Euler phi-function or Euler totient function of $n$ , denoted $φ (n)$ , is defined as following:

It is the order of the multiplicative group modulo $n$ , i.e., the multiplicative group of the ring of integers modulo $n$ .
It is the number of elements in ${1, 2, \dots, n}$ that are relatively prime to $n$ .

In terms of prime factorization

Suppose we have the following prime factorization of $n$ :

$n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ .

Then, we have:

$φ (n) = \prod_{i = 1}^{r} p_{i}^{k_{i}} (1 - \frac{1}{p_{i}})$ .

In other words:

$\frac{φ (n)}{n} = \prod_{i = 1}^{r} (1 - \frac{1}{p_{i}})$ .

Behavior

Upper bound

The largest values of $ϕ (n)$ are taken when $n$ is prime. $ϕ (p) = p - 1$ for a prime $p$ .

Thus:

$lim sup \frac{ϕ (p)}{p} = 1$ .

Lower bound

For any $ϵ > 0$ , there exists $N_{ϵ}$ such that:

$φ (n) \geq n^{1 - ϵ} \forall n \geq N_{ϵ}$ .

With the prime number theorem, we can find a constant $C$ such that:

Failed to parse (unknown function "\logn"): {\displaystyle \varphi(n) \ge n^{1 - (C\log\log n/\logn)}} .

Relation with other arithmetic functions

Universal exponent (also called Carmichael function) is the exponent of the multiplicative group modulo $n$ . The universal exponent of $n$ , usually denoted $λ (n)$ , divides $φ (n)$ .

Relations expressed in terms of Dirichlet products

$φ * U = E$ : In other words, the Dirichlet product of the Euler phi-function and the all ones function is the identity function:

$\sum_{d | n} φ (d) = n$ .

$φ = E * μ$ : 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:

$\sum_{d | n} d μ (n / d) = φ (n)$ .

$φ * τ = σ$ : In other words, the Dirichlet product of the Euler phi-function and the divisor count function equals the divisor sum function:

$\sum_{d | n} φ (d) τ (n / d) = σ (n)$ .

$σ * φ = E * E$ .

Relation with properties of numbers

Prime number: A number $n$ such that $φ (n) = n - 1$ .

@@ Line 41: / Line 41: @@
 <math>\varphi(n) \ge n^{1 - (C\log\log n/\logn)}</math>.
+==Relation with other arithmetic functions==
+* [[Universal exponent]] (also called Carmichael function) is the [[groupprops:exponent of a group|exponent]] of the multiplicative group modulo <math>n</math>. The universal exponent of <math>n</math>, usually denoted <math>\lambda(n)</math>, divides <math>\varphi(n)</math>.
+===Relations expressed in terms of Dirichlet products===
+* <math>\varphi * U = E</math>: In other words, the [[Dirichlet product]] of the Euler phi-function and the [[all ones function]] is the [[identity function]]:
+<math>\sum_{d|n} \varphi(d) = n</math>.
+* <math>\varphi = E * \mu</math>: 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]]:
+<math>\sum_{d|n} d\mu(n/d) = \varphi(n)</math>.
+* <math>\varphi * \tau = \sigma</math>: In other words, the [[Dirichlet product]] of the Euler phi-function and the [[divisor count function]] equals the divisor sum function:
+<math>\sum_{d|n} \varphi(d) \tau(n/d) = \sigma(n)</math>.
+* <math>\sigma * \varphi = E * E</math>.
+==Relation with properties of numbers==
+* [[Prime number]]: A number <math>n</math> such that <math>\varphi(n) = n-1</math>.