This site is supported by donations to The OEIS Foundation.

# Euler's totient function

Euler’s totient function
 φ (n)
counts how many positive integers from 1 to
 n
are coprime (relatively prime) to
 n
, or said to be orthogonal to
 n
, i.e. numbers that share no prime factors with
 n
.
${\displaystyle \varphi (n):=\sum _{{i=1} \atop {(n,i)=1}}^{n}1=\sum _{i=1}^{n}[(n,i)=1],}$
where
 (n, i )
is the greatest common divisor (GCD) of
 n
and
 i
, and
 [·]
is the Iverson bracket. A000010 Euler’s totient function
 φ (n), n   ≥   1,
(count of numbers up to
 n
and coprime to
 n
).
{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
 n, n   ≥   3,
are even, since
 k
is a totative if and only if
 n  −  k
is a totative, while
 n 2
obviously can’t be a totative of
 n
.
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
 π (n)
,[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
 n
that are coprime to
 n
are called the totatives of
 n
, while the integers from 1 to
 n
that are noncoprime to
 n
are called the cototatives of
 n
. Thus, the set of totatives of
 n
is (see coprimality triangle)
${\displaystyle \{1\leq i\leq n~|~(n,i)=1\},}$
while the set of cototatives of
 n
is
${\displaystyle \{1\leq i\leq n~|~(n,i)>1\},}$
where
 (n, i )
is the greatest common divisor (GCD) of
 n
and
 i
. Euler’s totient function is then the number of totatives of
 n
, while Euler’s cototient function is the number of cototatives of
 n
. Thus, Euler’s totient function is the cardinality of the set of totatives of
 n
:
${\displaystyle \varphi (n):=|\{1\leq i\leq n~|~(n,i)=1\}|,}$
while Euler’s cototient function is the cardinality of the set of cototatives of
 n
:
${\displaystyle {\overline {\varphi }}(n):=|\{1\leq i\leq n~|~(n,i)>1\}|.}$

## Properties

${\displaystyle \varphi (mn)=\varphi (m)\cdot \varphi (n),\quad (m,n)=1.}$
All totients for
 n   ≥   3
are even, since
 k
is a totative if and only if
 n  −  k
is a totative, while
 n 2
obviously can’t be a totative of
 n
.
Theorem.

Euler’s totient function is multiplicative. Given coprime integers
 m
and
 n
, the equation
 φ (m n) = φ (m) φ (n)
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
 m
by
 r1, r2, ..., rφ (m)
, and the one for
 n
by
 s1, s2, ..., sφ (n)
. If
 x
is in a residue system modulo
 m n
, it follows that
 gcd (x, m) = gcd (x, n) = 1
and so
 x   ≡   rh  (mod m)
and
 x   ≡   si  (mod n)
for some
 h
and
 i
. Per the Chinese remainder theorem, each pair of
 h
and
 i
determines just one possible
 x
modulo
 m n
. There are
 φ (m) φ (n)
possible pairs of
 h
and
 i
. This means that the reduced residue system modulo
 m n
has
 φ (m) φ (n)
terms and therefore
 φ (m n) = φ (m) φ (n)
as specified by the theorem.[6]
Note the requirement
 gcd (m, n) = 1
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.
 (n, 1) = 1, n   ≥   1,
thus
${\displaystyle \varphi (1)=1.}$
For a prime
 p
we have
${\displaystyle \varphi (p)=p-1.}$
For a prime power
 p α
we have
${\displaystyle \varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}=p^{\alpha -1}(p-1)=p^{\alpha }{\bigg (}1-{\frac {1}{p}}{\bigg )}=p^{\alpha }{\bigg (}{\frac {p-1}{p}}{\bigg )}.}$

Euler’s totient function being multiplicative, we get

${\displaystyle \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
 pi
are the distinct prime factors (that is, without multiplicity) of
 n
,
 ω (n)
is the number of distinct prime factors of
 n
and where for
 n = 1
we get 1 times the empty product 1.[7] The values of
 φ (n), n   ≥   1,
are given by A000010. Four special pairs
 (n, φ (n))
merit special attention:
•  φ (1) = 1
as the only case where  φ (n) = n
; for all higher  n
,  φ (n)   ≤   n  −  1
(with equality if and only if n is prime).
•  φ (2) = 1
and  φ (6) = 2
as the only two cases where  φ (n) < 2√  n
; for all other prime or composite  n
,  φ (n)   ≥   2√  n
.
•  φ (4) = 2
as the only case of a composite  n
such that  φ (n) = 2√  n
. For all composite  n > 6
we can sharpen the previously stated inequality to  φ (n) > 2√  n
.

### Euler’s cototient function

${\displaystyle {\overline {\varphi }}(n):=n-\varphi (n),}$
${\displaystyle {\overline {\varphi }}(n):=\sum _{{i=1} \atop {(n,i)\neq 1}}^{n}1=\sum _{i=1}^{n}[(n,i)\neq 1],}$
where
 (n, i )
is the greatest common divisor (GCD) of
 n
and
 i
, and
 [·]
is the Iverson bracket.

### Euler’s totient function and Dedekind psi function

Compare Euler’s totient function

${\displaystyle \varphi (n):=n\cdot {\prod _{p|n \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

${\displaystyle \psi (n):=n\cdot {\prod _{p|n \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
 φ (n)
is
${\displaystyle D_{\{\varphi (n)\}}(s)\equiv \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\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

${\displaystyle \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
 π (n)
is the prime counting function and (see A082695 for decimal expansion of
 A
)
${\displaystyle A=\sum _{j=1}^{\infty }{\frac {q(j)}{\varphi (j)}}\,{\frac {1}{j}}={\frac {\zeta (2)\,\zeta (3)}{\zeta (6)}}=1.9435964368207592\ldots }$
where
 q (n) = | μ (n) |
is the quadratfrei function and (see A?????? for decimal expansion of
 B
) (see A098468 for decimal expansion of
 − A B =  − 0.0605742294…
)
${\displaystyle 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).

(...)

### Totient summatory function

The totient summatory function (partial sums of Euler’s totient function) is

${\displaystyle \Phi (n):=\sum _{k=1}^{n}\varphi (k),\ n\geq 1,}$
where
 φ (n)
is Euler’s totient function. All values of the totient summatory function for
 n   ≥   2
are even.

### Cototient summatory function

The cototient summatory function (partial sums of Euler’s cototient function) is

${\displaystyle {\overline {\Phi }}(n):=\sum _{k=1}^{n}{\overline {\varphi }}(k),\ n\geq 1,}$
where
 x̅φ (n)
is Euler’s cototient function.

### Half difference of Dedekind psi function and Euler’s totient function

${\displaystyle {\frac {\psi (n)-\varphi (n)}{2}}={\frac {n}{2}}\cdot {{\bigg \{}{\prod _{p|n \atop p~{\rm {prime}}}{\bigg (}1+{\frac {1}{p}}{\bigg )}}-{\prod _{p|n \atop p~{\rm {prime}}}{\bigg (}1-{\frac {1}{p}}{\bigg )}}{\bigg \}}}.}$
Related sequences
 a (n), n   ≥   1.
A-number
 n
{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
 ψ (n)
{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
 φ (n)
{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
 ψ (n)  −  φ (n)
{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
 (ψ (n)  −  φ (n))  / 2
{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??????
n
p ∣n

 p ∣n
1 / p
{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
 n′
{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
 ψ (n)  −  φ (n) 2
is nearly identical with, at least for small
 n
, but is NOT A069359! The above data suggests that
 ψ (n)  −  φ (n) 2
is 0 only for
 n = 1
and 1 only when
 n
is prime. It also suggests that when
 n
is a prime power
 p k
that we get
 p k  − 1
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

${\displaystyle \psi (n)\cdot \varphi (n)=n^{2}\cdot {\prod _{p|n \atop p~{\rm {prime}}}{\bigg \{}{\bigg (}1+{\frac {1}{p}}{\bigg )}{\bigg (}1-{\frac {1}{p}}{\bigg )}{\bigg \}}}=n^{2}\cdot {\prod _{p|n \atop p~{\rm {prime}}}{\bigg (}1-{\frac {1}{p^{2}}}{\bigg )}}=n^{2}\cdot {\prod _{p|n \atop p~{\rm {prime}}}{\frac {p^{2}-1}{p^{2}}}}={\bigg (}{\frac {n}{{\rm {rad}}(n)}}{\bigg )}^{2}\cdot {\prod _{p|n \atop p~{\rm {prime}}}(p^{2}-1)},}$
where
is the squarefree kernel of
 n
. Since
 p 2  −  1
is divisible by 24 (see A024702) when
 p
is congruent to 1 or 5 modulo 6 and (2 2  −  1) (3 2  −  1) = 24, we deduce that
 ψ (n) ⋅  φ (n)
is divisible by
 24 ω (n)
if
 n
is divisible by neither 2 nor 3 or both 2 and 3, and is divisible by
 24 ω (n)  − 1
if
 n
is divisible by either (but not both) 2 or 3,
 ω (n)
being the number of distinct prime factors of
 n
.

### Quotient of the Dedekind psi function by Euler’s totient function

The quotient of the Dedekind psi function by Euler’s totient function gives

${\displaystyle {\frac {\psi (n)}{\varphi (n)}}={\prod _{p|n \atop p~{\rm {prime}}}{\frac {{\bigg (}1+{\frac {1}{p}}{\bigg )}}{{\bigg (}1-{\frac {1}{p}}{\bigg )}}}}={\prod _{p|n \atop p~{\rm {prime}}}{\bigg (}{\frac {p+1}{p-1}}{\bigg )}}.}$

## Sequences

A092249 The totient summatory function (partial sums of Euler’s totient function) (see A002088 for
 n   ≥   0
). (All values for
 n   ≥   2
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
 n
taken by the totient function
 φ (m)
(A000010) for some
 m   ≥   1
. (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
 n
such that
 φ (m) = n
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
 n
such that
 φ (m) = n
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
 k
having more solutions to the equation
 φ (x) = k
than any preceding
 k
).
{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
 φ (n)
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
 n
s.t. the sum of the totient function values taken over all iterations adds up to
 n
).
{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
 n
, 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, ...}