Francais | English | Espanõl

Euler's totient function

From Wikipedia, the free encyclopedia

(Redirected from Euler's phi function)
Jump to: navigation, search
For other meanings, see Euler function (disambiguation).
Image:EulerPhi.PNG

In number theory, the totient <math>\phi(n)</math> of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. For example, <math>\phi(8) = 4</math> since the four numbers 1, 3, 5 and 7 are coprime to 8. The function <math>\phi</math> so defined is the totient function. The totient is usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it. The totient function is also called Euler's phi function or simply the phi function, since the letter Phi (<math>\phi</math>) is so commonly used for it. The cototient of n is defined as <math>n - \phi(n)</math>.

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, <math>\phi(n)</math> is the order of the group of units of the ring <math>\mathbb{Z}/n\mathbb{Z}</math>. This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.

Contents

[edit] Computing Euler's function

It follows from the definition that <math>\phi(1) = 1</math>, and <math>\phi(n) = (p - 1)p^{k - 1}</math> when n is the kth power of a prime number p. Moreover, <math>\phi</math> is a multiplicative function; if m and n are coprime then <math>\phi(mn) = \phi(m) \phi(n)</math>. (Sketch of proof: let A, B, C be the sets of residue classes modulo-and-coprime-to m, n, mn respectively; then there is a bijection between <math>A \times B</math> and <math>C</math>, via the Chinese remainder theorem.) The value of <math>\phi(n)</math> can thus be computed using the fundamental theorem of arithmetic: if

<math>n = p_1^{k_1} \cdots p_r^{k_r}</math>

where the <math>p_j</math> are distinct primes, then

<math>\phi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}</math>

This last formula is a Euler product and is often written as

<math>\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>

with the product ranging only over the distinct primes pr.

[edit] Computing example

<math>\phi(36)=\phi(3^22^2)=36\left(1-\frac{1}{3}\right)\left(1-\frac{1}{2}\right)=36\cdot\frac{2}{3}\cdot\frac{1}{2}=12</math>

[edit] Some values of the function

<math>\phi(n)</math> +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88

[edit] Properties

The number <math>\phi(n)</math> is also equal to the number of possible generators of the cyclic group <math>C_n</math> (and therefore also to the degree of the cyclotomic polynomial <math>\phi_n</math>). Since every element of <math>C_n</math> generates a cyclic subgroup and the subgroups of <math>C_n</math> are of the form <math>C_d</math> where d divides n (written as <math>d | n</math>), we get

<math>\sum_{d\mid n}\phi(d)=n</math>

where the sum extends over all positive divisors d of n.

We can now use the Möbius inversion formula to "invert" this sum and get another formula for <math>\phi(n)</math>:

<math>\phi(n)=\sum_{d\mid n} d \cdot \mu(n/d) </math>

where <math>\mu</math> is the usual Möbius function defined on the positive integers.

According to Euler's theorem, if a is coprime to n, that is, gcd(a,n) = 1, then

<math> a^{\phi(n)} \equiv 1\mod n.</math>

This follows from Lagrange's theorem and the fact that a belongs to the multiplicative group of <math>\mathbb{Z}/n\mathbb{Z}</math> iff a is coprime to n.

[edit] Generating functions

The two generating functions presented here are both consequences of the fact that

<math>\sum_{d|n} \phi(d) = n.</math>

A Dirichlet series involving <math>\phi</math>(n) is

<math>\sum_{n=1}^\infty \frac{\phi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math>

This is derived as follows:

<math> \zeta(s) \sum_{n=1}^\infty \frac{\phi(n)}{n^s} =

\sum_{n=1}^\infty \left(\sum_{d|n} \phi(d)\right) \frac{1}{n^s} = \sum_{n=1}^\infty \frac{n}{n^s} = \zeta(s-1),</math>

where <math>\zeta(s)</math> is the Riemann Zeta function.

A Lambert series generating function is

<math>\sum_{n=1}^{\infty} \frac{\phi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math>

which converges for |q|<1.

This follows from

<math>\sum_{n=1}^{\infty} \frac{\phi(n) q^n}{1-q^n} =

\sum_{n=1}^{\infty} \phi(n) \sum_{r\ge 1} q^{rn}</math>

which is

<math>

\sum_{k\ge 1} q^k \sum_{n|k} \phi(n) = \sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.</math>

[edit] Growth of the function

The growth of <math>\phi(n)</math> as a function of n is an interesting question, since the first impression from small n that <math>\phi(n)</math> might be noticeably smaller than n is somewhat misleading. Asymptotically we have

<math>\,n^{1-\epsilon}<\phi(n)<n</math>

for any given <math>\epsilon > 0</math> and <math>n > N(\epsilon)</math>. In fact if we consider

<math>\,\phi(n)/n</math>

we can write that, from the formula above, as the product of factors

<math>1-p^{-1}\,</math>

taken over the prime numbers p dividing n. Therefore the values of n corresponding to particularly small values of the ratio are those n that are the product of an initial segment of the sequence of all primes. From the prime number theorem it can be shown that a constant ε in the formula above can therefore be replaced by

<math>C\,\log \log n/ \log n</math>

<math>\phi</math> is also generally close to n in an average sense:

<math>\frac{1}{n^2} \sum_{k=1}^n \phi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)</math>

where the big O is the Landau symbol. This also says that the probability of two positive integers chosen at random from {1,2,...,n} being relatively prime approaches <math>6/\pi^2</math> when n tends to infinity. A related result is the average order of <math>\phi(n)/n</math>, which is described by

<math>\frac{1}{n} \sum_{k=1}^n \frac{\phi(k)}{k} =

\frac{6}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)</math> A proof of these two formulas may be found here.

[edit] Other formulas involving Euler's function

<math>\;\phi(n^m) = n^{m-1}\phi(n)</math> for <math>m\ge 1</math>
<math>\sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)} = \frac{n}{\phi(n)}</math>
<math>\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\phi(n)</math> for <math>\;n>1</math>
<math>\sum_{k=1}^n\phi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)</math>
<math>\sum_{k=1}^n\frac{\phi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor</math>
<math>\sum_{k=1}^n\frac{k}{\phi(k)} = \mathcal{O}(n)</math>
<math>\sum_{k=1}^n\frac{1}{\phi(k)} = \mathcal{O}(\log(n))</math>

Proofs of some of these identities may be found here.

[edit] Inequalities

Some inequalities involving the <math>\phi</math> function are:

<math>

\phi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} </math> for n > 2, where γ is Euler's constant,

<math>

\phi(n) \ge \sqrt{\frac {n} {2} } </math> for n > 0,

and

<math>

\phi(n) \ge \sqrt{n} </math> for n > 6.

For prime n, clearly <math>\phi(n) = n-1</math>. For composite n we have

<math>

\phi(n) \le n-\sqrt{n} </math> (for composite n).

For all <math>n>1 </math>:

<math>0<\frac{\phi (n)}{n}<1 </math>

For randomly large n, these bounds still cannot be improved, or to be more precise :

<math>\liminf \frac{\phi (n)}{n}=0 \mbox{ and } \limsup \frac{\phi (n)}{n}=1. </math>

A pair of inequalities combining the <math>\phi</math> function and the <math>\sigma</math> divisor function are:

<math>

\frac {6 n^2}{\pi^2} < \phi(n) \sigma(n) < n^2 \mbox{ for } n>1. </math>

The last two are proved on the page on proofs of totient identities.

[edit] See also

[edit] References

  • Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 0-486-61272-4. See paragraph 24.3.2.
  • Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.

ca:Funció Fi d'Euler cs:Eulerova funkce da:Eulers totientfunktion de:Eulersche φ-Funktion es:Función φ de Euler fr:Indicatrice d'Euler ko:오일러 파이 함수 it:Funzione phi di Eulero he:פונקציית אוילר hu:Euler-függvény nl:Indicator (getaltheorie) ja:オイラーのφ関数 pl:Funkcja φ pt:Função totiente de Euler ru:Функция Эйлера sl:Eulerjeva funkcija fi sv:Eulers phi-funktion tr:Totient zh:欧拉函数

Retrieved from "http://en.wikivisual.com/index.php/Euler%27s_totient_function"
Personal tools