Euler's totient function Information & Euler's totient function Links at HealthHaven.com

For other functions named after Euler, see List of topics named after Leonhard Euler.

The first thousand values of $\varphi(n)$

In number theory, the totient $\varphi(n)$ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. In particular $\varphi(1)=1$ since 1 is coprime to itself (1 being the only natural number with this property). For example, $\varphi(9)=6$ since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9. The function $\varphi$ 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 it is commonly denoted by the Greek letter phi ( $\varphi$ ). The cototient of n is defined as $n - \varphi(n)$ , in other words the number of positive integers less than n that are not coprime to n.

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, $\varphi(n)$ is the order of the group of units of the ring $\mathbb{Z}/n\mathbb{Z}$ . This fact, together with Lagrange's theorem on the possible sizes of subgroups of a group, provides a proof for Euler's theorem that $a^{\varphi(n)}\equiv 1 \pmod{n}$ for all a coprime to n. The totient function also plays a key role in the definition of the RSA encryption system.

[edit] Computing Euler's function

If p is prime, then for integer $k\ge1, \varphi(p^{k}) = (p - 1)p^{k - 1}$ . Moreover, $\varphi$ is a multiplicative function; if m and n are coprime then $\varphi(mn) = \varphi(m) \varphi(n)$ . (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 A × B and C, by the Chinese remainder theorem.) The value of $\varphi(n)$ can thus be computed using the fundamental theorem of arithmetic: if

$n = p_1^{k_1} \cdots p_r^{k_r}$

where the p_j are distinct primes, then

$\varphi(n)=(p_1-1)p_1^{k_1-1} \cdots (p_r-1)p_r^{k_r-1}.$

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

$\varphi(n)= n \cdot \prod_{p|n} \left( 1-\frac{1}{p} \right)$

with the product ranging only over the distinct primes p dividing n.

[edit] Computing example

$\varphi(36)=\varphi\left(2^2 3^2\right)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=36\cdot\frac{1}{2}\cdot\frac{2}{3}=12.$

In words, this says that the distinct prime factors of 36 are 2 and 3; half of the thirty-six integers from 1 to 36 are divisible by 2, leaving eighteen; a third of those are divisible by 3, leaving twelve coprime to 36. And indeed there are twelve: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.

Moreover W. Schramm has shown that:

$\varphi (n)=\sum\limits_{k=1}^n{\operatorname{gcd}(k,n)\cdot \exp \left(\frac{-2\pi ik}{n}\right)}.$

[edit] Some values of the function

The first few values (sequence A000010 in OEIS) are shown in the table and graph below:

Run chart of the first 100 values

$\varphi(n)$	+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
90+	24	72	44	60	46	72	32	96	42	60

[edit] Implementation

[edit] Implementation in C

This is an implementation of the totient function for a non-negative 64-bit integer argument n written in C using the sieve of Eratosthenes to determine the prime factors and the method described above. It depends upon a binary GCD C implementation (uint64 bgcdll(uint64,uint64)) and an integer square root function (uint64 sqrtll(uint64)). Sieve factorization methods are efficient for small numbers (12 digits or so), but inefficient for larger numbers. For example, totient(9223372036854775837LL) requires many tens of seconds on a modern computer, whereas more efficient algorithms require a tiny fraction of this time. Thus, this implementation is practical for small integers, but impractical over the full 64-bit full range.

 typedef unsigned long long uint64; typedef unsigned char uint8;   #define TOTIENT_TABLE_SIZE 20 static unsigned short int totient_table[TOTIENT_TABLE_SIZE] = { /* phi(1), phi(2), ... */        1,    1,    2,    2,    4,    2,    6,    4,    6,    4,       10,    4,   12,    6,    8,    8,   16,    6,   18,    8 };   uint64 totient(uint64 n) /* Return Euler's totient function. */ {     uint64 sqrtll(uint64),bgcdll(uint64,uint64);     uint64 res=1,p,phip,pf=1,sqrtn=sqrtll(n);     uint8 pflag;       if (n <= 0) return 0;  /* Really DATA ERROR by Fundamental Theorem of Arithmetic  */     if (n <= TOTIENT_TABLE_SIZE) return totient_table[n-1];       for (p=2;;) {         phip=p-1;         pflag=0;         while (n%p == 0) {  /* phi(p^k) = p^(k-1)*(p-1) */             if (!pflag && !(bgcdll(pf,p) == 1)) break;             res *= phip;             phip = p;             n = n/p;             if (!pflag) pf *= p;             pflag = 1;         }         if (pflag) sqrtn = sqrtll(n);         p = (p > 2)? p+2 : 3;         if (p > sqrtn) break;     }     /* n is necessarily 1 or a distinct prime */     if (n > 1) res *= (n-1);       return res; }   /* Integer square root based upon http://www.codecodex.com/wiki/Calculate_an_integer_square_root */ uint64 sqrtll(uint64 x) /* Return the integer square root. */ {     uint64 op=x,res=0,one;       /* "one" starts at the highest power of four <= than the argument. */     one = (uint64)1 << (8*sizeof(uint64)-2);  /* second-to-top bit set */     while (one > op) one >>= 2;       while (one != 0) {         if (op >= res + one) {             op = op - (res + one);             res = res + (one+one);         }         res >>= 1;         one >>= 2;     }     return res; }

[edit] Properties

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

$\sum_{d\mid n}\varphi(d)=n$

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 $\varphi(n)$ :

$\varphi(n)=\sum_{d\mid n} d \cdot \mu\left(\frac{n}{d} \right)$

where μ 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

$a^{\varphi(n)} \equiv 1\mod n.\,$

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

[edit] Generating functions

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

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

A Dirichlet series involving $\varphi$ (n) is

$\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}$

where ζ(s) is the Riemann zeta function. This is derived as follows:

$\zeta(s) \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \left(\sum_{g=1}^\infty \frac{1}{g^s}\right)\left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right)$

$\left(\sum_{g=1}^\infty \frac{1}{g^s}\right) \left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right) = \sum_{h=1}^\infty \left(\sum_{fg=h} 1 \cdot \varphi(g)\right) \frac{1}{h^s}$

$\sum_{h=1}^\infty \left(\sum_{fg=h} \varphi(g) \right) \frac{1}{h^s} = \sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d) \right) \frac{1}{h^s}$

$\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d) \right) \frac{1}{h^s} =$ $\sum_{h=1}^\infty\frac{h}{h^s}$

$\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1).$

A Lambert series generating function is

$\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}$

which converges for |q|<1.

This follows from

$\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} = \sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}$

which is

$\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) = \sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.$

[edit] Growth of the function

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

$\,n^{1-\varepsilon}<\varphi(n)<n$

for any given ε > 0 and n > N(ε). In fact if we consider

$\,\varphi(n)/n,$

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

$1-p^{-1}\,$

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

$C\,\log \log n/ \log n.$

$\varphi$ is also generally close to n in an average sense:

$\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)$

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

$\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} = \frac{6}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)$

Because $\frac{6}{\pi^2} = \frac{1}{\zeta(2)}$ , one can also express the formula this way.

$\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} = \frac{1}{\zeta(2)} + \mathcal{O}\left(\frac{\log n }{n}\right)$

A proof of these formulas may be found here.

[edit] Other formulas involving Euler's function

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n) \text{ for } m\ge 1$

$\text{For any } a, n > 1 \text{, } n|\varphi(a^n-1)$

$\text{For any } a > 1 \text{ and } n > 6 \text{ such that } 4 \not| n \text{ there exists an } l \geq 2n \text{ such that } l|\varphi(a^n-1)$

$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$

$\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1$ See proof here.

$\sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)$

$\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor$

$\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)$

$\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))$

$\sum_{1\le k\le n \atop (k,m)=1} 1 = n \frac {\varphi(m)}{m} + \mathcal{O} \left ( 2^{\omega(m)} \right ),$

where m > 1 is a positive integer and ω(m) designates the number of distinct prime factors of m. (This formula counts the number of naturals less than or equal to n and relatively prime to m, additional material is listed among the external links.)

Proofs of some of these identities may be found here.

[edit] Inequalities

Some inequalities involving the $\varphi$ function are:

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

$\varphi(n) \ge \sqrt{\frac {n} {2} }$ for n > 0,

and

$\varphi(n) \ge \sqrt{n}\text{ for } n > 6.$

For prime n, clearly $\varphi(n) = n-1$ .

For a composite number n we have

$\varphi(n) \le n-\sqrt{n}$ .

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

$\liminf \frac{\varphi (n)}{n}=0 \mbox{ and } \limsup \frac{\varphi (n)}{n}=1.$

A pair of inequalities combining the $\varphi$ function and the $σ$ divisor function are:

$\frac {6 n^2}{\pi^2} < \varphi(n) \sigma(n) < n^2 \mbox{ for } n>1.$

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

[edit] Ford's theorem

Ford (1999) proved that for every integer k ≥ 2 there is a number m for which the equation φ(x) = m has exactly k solutions; this result had previously been conjectured by Wacław Sierpiński. However, no such m is known for k = 1, and according to Carmichael's totient function conjecture it is believed that in this case no such m exists.

[edit] See also

[edit] References

Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4 . See paragraph 24.3.2.

Bach, E.; Shallit, J. (1996), Algorithmic Number Theory, 1, Cambridge, MA: MIT Press, ISBN 0-262-02405-5 . See page 234 in section 8.8.

Ford, K. (1999), "The number of solutions of φ(x) = m", Annals of Mathematics 150 (1): 283–311, doi:10.2307/121103, MR 1715326 .

Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory A50 (8(1)), http://www.integers-ejcnt.org/vol8.html .

[edit] External links

Kirby Urner, Computing totient function in Python and scheme, (2003)
Simple java script totient calculator , [1]
Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
Bordellès, Olivier, Numbers prime to q in $[1, n]$
Calculate φ(n) for a number up to 2³¹ [2]
Plytage, Loomis, Polhill Summing Up The Euler Phi Function
Fabrizio Romano, a faster python implementation [3]

Contents