Euler’s totient function counts how many
positive integers from
1 to
are
coprime (relatively prime) to
, or said to be
orthogonal to
, i.e. numbers that share no
prime factors with
.
 $\varphi (n):=\sum _{{i=1} \atop {(n,i)=1}}^{n}1=\sum _{i=1}^{n}[(n,i)=1],$
where
is the
greatest common divisor (GCD) of
and
, and
is the
Iverson bracket.
A000010 Euler’s totient function
(count of numbers up to
and coprime to
).

{1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, ...}
All totients for
are even, since
is a totative if and only if
is a
totative, while
obviously can’t be a totative of
.
Also called
Euler’s function,
^{[1]} or
Euler’s phi function or just
totient function and sometimes even
Euler’s function.
^{[2]} The function was first studied by
Leonhard Euler in 1749 in connection to a problem in
congruences,
^{[3]} he notated it as
,
^{[4]} but today we follow
Carl Friedrich Gauss’s alternate notation with the
Greek letter (phi).
^{[5]}
Totatives and cototatives
 Main article page: Totatives and cototatives
The integers from
1 to
that are
coprime to
are called the totatives of
, while the integers from
1 to
that are noncoprime to
are called the cototatives of
.
Thus, the set of totatives of
is (see
coprimality triangle)
 $\{1\leq i\leq n~~(n,i)=1\},$
while the set of
cototatives of
is
 $\{1\leq i\leq n~~(n,i)>1\},$
where
is the
greatest common divisor (GCD) of
and
.
Euler’s totient function is then the number of
totatives of
, while
Euler’s cototient function is the number of
cototatives of
.
Thus, Euler’s totient function is the
cardinality of the set of totatives of
:
 $\varphi (n):=\{1\leq i\leq n~~(n,i)=1\},$
while Euler’s cototient function is the
cardinality of the set of cototatives of
:
 ${\overline {\varphi }}(n):=\{1\leq i\leq n~~(n,i)>1\}.$
Properties
Euler’s totient function is a multiplicative arithmetic function, e.g.
 $\varphi (mn)=\varphi (m)\cdot \varphi (n),\quad (m,n)=1.$
All totients for
are even, since
is a totative if and only if
is a
totative, while
obviously can’t be a totative of
.
Theorem.
Euler’s totient function is multiplicative. Given coprime integers and , the equation holds.
Proof. Remember that Euler’s totient function counts how many members the reduced residue system modulo a given number has. Designate the reduced residue system modulo by , and the one for by . If is in a residue system modulo , it follows that gcd (x, m) = gcd (x, n) = 1 
and so and for some and . Per the Chinese remainder theorem, each pair of and determines just one possible modulo . There are possible pairs of and . This means that the reduced residue system modulo has terms and therefore as specified by the theorem.^{[6]} □
Note the requirement
is needed: Euler’s totient function is not completely multiplicative.
Formulae
Euler’s totient function
Since
1 has no
prime factors (it is the
empty product of prime factors), it is then
coprime to any integer, including itself, i.e.
thus
 $\varphi (1)=1.$
For a
prime we have
 $\varphi (p)=p1.$
For a
prime power we have
 $\varphi (p^{\alpha })=p^{\alpha }p^{\alpha 1}=p^{\alpha 1}(p1)=p^{\alpha }{\bigg (}1{\frac {1}{p}}{\bigg )}=p^{\alpha }{\bigg (}{\frac {p1}{p}}{\bigg )}.$
Euler’s totient function being multiplicative, we get
 $\varphi (n)=\varphi {\bigg (}\ {\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i}}}{\bigg )}=\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i}}{\bigg (}1{\frac {1}{p_{i}}}{\bigg )}=n\prod _{i=1}^{\omega (n)}{\bigg (}1{\frac {1}{p_{i}}}{\bigg )}=n\prod _{i=1}^{\omega (n)}{\bigg (}{\frac {p_{i}1}{p_{i}}}{\bigg )},$
where the
are the distinct prime factors (that is, without
multiplicity) of
,
is the
number of distinct prime factors of
and where for
we get
1 times the
empty product 1.
^{[7]}
The values of
are given by
A000010. Four special pairs
merit special attention:
 as the only case where ; for all higher , (with equality if and only if n is prime).
 and as the only two cases where ; for all other prime or composite , .
 as the only case of a composite such that . For all composite we can sharpen the previously stated inequality to .
Euler’s cototient function
 ${\overline {\varphi }}(n):=n\varphi (n),$
 ${\overline {\varphi }}(n):=\sum _{{i=1} \atop {(n,i)\neq 1}}^{n}1=\sum _{i=1}^{n}[(n,i)\neq 1],$
where
is the
greatest common divisor (GCD) of
and
, and
is the
Iverson bracket.
Euler’s totient function and Dedekind psi function
Compare Euler’s totient function
 $\varphi (n):=n\cdot {\prod _{pn \atop p~{\rm {prime}}}{\bigg (}1{\frac {1}{p}}{\bigg )}}\,=\,n\cdot \prod _{i=1}^{\omega (n)}{\bigg (}1{\frac {1}{p_{i}}}{\bigg )},$
with Dedekind psi function, which is defined by the formula
 $\psi (n):=n\cdot {\prod _{pn \atop p~{\rm {prime}}}{\bigg (}1+{\frac {1}{p}}{\bigg )}}\,=\,n\cdot \prod _{i=1}^{\omega (n)}{\bigg (}1+{\frac {1}{p_{i}}}{\bigg )}.$
The totient function is multiplicative,^{[8]} and accordingly A000010 has keyword:mult.
Generating function
Dirichlet generating function
The
Dirichlet generating function of
is
 $D_{\{\varphi (n)\}}(s)\equiv \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s1)}{\zeta (s)}}={\frac {\zeta (2s)}{(\zeta (s))^{2}}}\cdot D_{\{\psi (n)\}}(s).$
Harmonic series of totients
The harmonic series of totients (sum of reciprocals of the totients) diverges
 $\sum _{i=1}^{n}{\frac {1}{\varphi (i)}}A\,(\log n+B)\sim O\left({\frac {\log n}{n}}\right)\sim O\left({\frac {1}{\pi (n)}}\right),$
where
is the
prime counting function and (see
A082695 for decimal expansion of
)
 $A=\sum _{j=1}^{\infty }{\frac {q(j)}{\varphi (j)}}\,{\frac {1}{j}}={\frac {\zeta (2)\,\zeta (3)}{\zeta (6)}}=1.9435964368207592\ldots$
where
is the
quadratfrei function and (see A?????? for decimal expansion of
) (see
A098468 for decimal expansion of
)
 $B=\gamma \,\,\sum _{j=1}^{\infty }{\frac {q(j)}{\varphi (j)}}\,{\frac {\log j}{j}}=0.57721566\ldots \,\,0.60838171786\ldots =0.03116605\ldots$
and where
(
A001620) is the
Euler–Mascheroni constant and the second term’s decimal expansion is given by
A085609.
Related functions
Iterated Euler totient function
The totient function can be iterated until it reaches 1; A003434 counts how many iterations it takes. We can add up the iterations of the totient function; numbers that add up to themselves are called perfect totient numbers (see A082897).
Iterated Euler cototient function
(...)
Totient summatory function
The totient summatory function (partial sums of Euler’s totient function) is
 $\Phi (n):=\sum _{k=1}^{n}\varphi (k),\ n\geq 1,$
where
is Euler’s totient function.
All values of the totient summatory function for
are even.
Cototient summatory function
The cototient summatory function (partial sums of Euler’s cototient function) is
 ${\overline {\Phi }}(n):=\sum _{k=1}^{n}{\overline {\varphi }}(k),\ n\geq 1,$
where
is Euler’s cototient function.
Half difference of Dedekind psi function and Euler’s totient function
 ${\frac {\psi (n)\varphi (n)}{2}}={\frac {n}{2}}\cdot {{\bigg \{}{\prod _{pn \atop p~{\rm {prime}}}{\bigg (}1+{\frac {1}{p}}{\bigg )}}{\prod _{pn \atop p~{\rm {prime}}}{\bigg (}1{\frac {1}{p}}{\bigg )}}{\bigg \}}}.$
Related sequences


Anumber


{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, ...}

A000027


{1, 3, 4, 6, 6, 12, 8, 12, 12, 18, 12, 24, 14, 24, 24, 24, 18, 36, 20, 36, 32, 36, 24, 48, 30, 42, 36, 48, 30, 72, 32, 48, 48, 54, 48, 72, ...}

A001615


{1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, ...}

A000010


{0, 2, 2, 4, 2, 10, 2, 8, 6, 14, 2, 20, 2, 18, 16, 16, 2, 30, 2, 28, 20, 26, 2, 40, 10, 30, 18, 36, 2, 64, 2, 32, 28, 38, 24, 60, ...}

A292786


{0, 1, 1, 2, 1, 5, 1, 4, 3, 7, 1, 10, 1, 9, 8, 8, 1, 15, 1, 14, 10, 13, 1, 20, 5, 15, 9, 18, 1, 32, 1, 16, 14, 19, 12, 30, ...}

A??????


{0, 1, 1, 2, 1, 5, 1, 4, 3, 7, 1, 10, 1, 9, 8, 8, 1, 15, 1, 14, 10, 13, 1, 20, 5, 15, 9, 18, 1, 31, 1, 16, 14, 19, 12, 30, ...}

A069359


{0, 1, 1, 4, 1, 5, 1, 12, 6, 7, 1, 16, 1, 9, 8, 32, 1, 21, 1, 24, 10, 13, 1, 44, 10, 15, 27, 32, 1, 31, 1, 80, 14, 19, 12, 60, ...}

A003415

The sequence for
is nearly identical with, at least for small
, but is NOT
A069359!
The above data suggests that
is
0 only for
and
1 only when
is
prime. It also suggests that when
is a
prime power that we get
in the sequence.
Product of the Dedekind psi function with Euler’s totient function
The product of the Dedekind psi function with Euler’s totient function gives
 $\psi (n)\cdot \varphi (n)=n^{2}\cdot {\prod _{pn \atop p~{\rm {prime}}}{\bigg \{}{\bigg (}1+{\frac {1}{p}}{\bigg )}{\bigg (}1{\frac {1}{p}}{\bigg )}{\bigg \}}}=n^{2}\cdot {\prod _{pn \atop p~{\rm {prime}}}{\bigg (}1{\frac {1}{p^{2}}}{\bigg )}}=n^{2}\cdot {\prod _{pn \atop p~{\rm {prime}}}{\frac {p^{2}1}{p^{2}}}}={\bigg (}{\frac {n}{{\rm {rad}}(n)}}{\bigg )}^{2}\cdot {\prod _{pn \atop p~{\rm {prime}}}(p^{2}1)},$
where
is the
squarefree kernel of
.
Since
is divisible by
24 (see
A024702) when
is congruent to
1 or
5 modulo
6 and
(2 2 − 1) (3 2 − 1) = 24, we deduce that
is divisible by
if
is divisible by neither
2 nor
3 or both
2 and
3, and is divisible by
if
is divisible by either (but not both)
2 or
3,
being the
number of distinct prime factors of
.
Quotient of the Dedekind psi function by Euler’s totient function
The quotient of the Dedekind psi function by Euler’s totient function gives
 ${\frac {\psi (n)}{\varphi (n)}}={\prod _{pn \atop p~{\rm {prime}}}{\frac {{\bigg (}1+{\frac {1}{p}}{\bigg )}}{{\bigg (}1{\frac {1}{p}}{\bigg )}}}}={\prod _{pn \atop p~{\rm {prime}}}{\bigg (}{\frac {p+1}{p1}}{\bigg )}}.$
Sequences
A092249 The
totient summatory function (partial sums of Euler’s totient function) (see
A002088 for
). (All values for
are even.)

{1, 2, 4, 6, 10, 12, 18, 22, 28, 32, 42, 46, 58, 64, 72, 80, 96, 102, 120, 128, 140, 150, 172, 180, 200, 212, 230, 242, 270, 278, 308, 324, 344, 360, 384, 396, 432, 450, 474, 490, 530, 542, 584, 604, ...}
A002202 The totients, i.e. values
taken by the totient function
(
A000010) for some
. (Note that
1 is the only odd value returned by the function.)

{1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100, 102, 104, 106, 108, 110, 112, 116, 120, 126, 128, 130, ...}
A007617 The nontotients, i.e. values not in range of Euler’s totient function. (Note that all odd values greater than 1 are nontotients.)

{3, 5, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 45, 47, 49, 50, 51, 53, 55, 57, 59, 61, 62, 63, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 83, 85, 86, 87, ...}
A005277 The even nontotients (even
such that
has no solution).

{14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, ...}
A005277 The odd nontotients (odd
such that
has no solution). (All the odd numbers greater than
1 (
A144396).)

{3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, ...}
A097942 The highly totient numbers (numbers
having more solutions to the equation
than any preceding
).

{1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640, 11520, 17280, 25920, 30240, 34560, 40320, 51840, 60480, 69120, 80640, 103680, 120960, 161280, ...}
A003434 The number of iterations of
needed to reach
1.

{0, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5, 5, 5, 6, 5, 5, 5, 6, 5, 6, 4, 6, 5, 5, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 6, 5, 6, 5, 6, 5, 6, 5, 6, ...}
A082897 The perfect totient numbers (numbers
s.t. the sum of the totient function values taken over all iterations adds up to
).

{3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, ...}
A?????? (
Dedekind psi function − Euler’s totient function) /
2. (It is nearly identical, at least for small
, but is NOT
A069359!)

{0, 1, 1, 2, 1, 5, 1, 4, 3, 7, 1, 10, 1, 9, 8, 8, 1, 15, 1, 14, 10, 13, 1, 20, 5, 15, 9, 18, 1, 32, 1, 16, 14, 19, 12, 30, ...}
See also
Notes
 ↑ Harold M. Stark, An Introduction to Number Theory. Chicago: Markham Publishing Company (1970) p. 77.
 ↑ R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective. New York: Springer (2001) p. 119.
 ↑ H. E. Rose, A Course in Number Theory. Oxford: Clarendon Press (1988) p. 21.
 ↑ D. N. Lehmer, “Dickson’s History of the Theory of Numbers” Bull. Amer. Math. Soc. 26 3 (1919), 128.
 ↑ Stark, p. 78.
 ↑ Ivan Niven & Herbert S. Zuckerman, An Introduction to the Theory of Numbers. New York: John Wiley & Sons (1980) p. 48, Section 2.4, Theorem 2.15.
 ↑ For the derivation of this formula see equations (1) to (12) of: Weisstein, Eric W., Totient Function, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/TotientFunction.html].
 ↑ Stark, p. 83, Theorem 3.15