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 or equal to
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
unit 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.
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 moduloandcoprimeto
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_11)p_1^{k_11} \cdots (p_r1)p_r^{k_r1}.
This last formula is an
Euler product
and is often written as
 \varphi(n)= n \cdot \prod_{pn} \left( 1\frac{1}{p}
\right)
with the product ranging only over the distinct primes
p
dividing
n.
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 thirtysix 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)}.
Some values of the function
The first few values are shown in the table and graph below:
\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 
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.
Generating functions
The two
generating functions
presented here are both consequences of the fact that
 \sum_{dn} \varphi(d) = n.
A
Dirichlet series involving
\varphi(
n) is
 \sum_{n=1}^\infty
\frac{\varphi(n)}{n^s}=\frac{\zeta(s1)}{\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_{dh} \varphi(d)
\right) \frac{1}{h^s}
 \sum_{h=1}^\infty \left(\sum_{dh} \varphi(d) \right)
\frac{1}{h^s} =\sum_{h=1}^\infty\frac{h}{h^s}
 \sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s1).
A
Lambert series generating function
is
 \sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1q^n}=
\frac{q}{(1q)^2}
which converges for 
q<1.></1.>
This follows from
 \sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}
which is
\sum_{k\ge 1} q^k \sum_{nk} \varphi(n) =\sum_{k\ge 1} k q^k =
\frac{q}{(1q)^2}.
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)</\VARPHI(N)math>
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
 1p^{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.
Other formulas involving Euler's function
 \;\varphi\left(n^m\right) = n^{m1}\varphi(n) \text{ for } m\ge
1
 \text{For any } a, n > 1 \text{, } n\varphi(a^n1)
 \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^n1)
 \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.
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) = n1.
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
\sigma
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.
Ford's theorem
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.
See also
References
 . See page 234 in section 8.8.
External links
 Kirby Urner, Computing totient function in Python and
scheme, (2003)
 Simple java script totient calculator , [8577]
 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^{31} [8578]
 Plytage, Loomis, Polhill Summing Up The Euler Phi Function
 Fabrizio Romano, a faster python implementation [8579]