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
.
φ (n)  :=
 n ∑ i  = 1(n, i )  = 1

1  =
 n ∑ i  = 1

[ (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)
 {1 ≤ i ≤ n | (n, i ) = 1},
while the set of cototatives of
 n
is
 {1 ≤ i ≤ 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
:
 φ (n)  :=  | {1 ≤ i ≤ n | (n, i ) = 1} | ,
while Euler’s cototient function is the cardinality of the set of cototatives of
 n
:
 x̅φ (n)  :=  | {1 ≤ i ≤ n | (n, i ) > 1} | .

## Properties

 φ (m n)  =  φ (m)  ⋅  φ (n), (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
 φ (1)  =  1.
For a prime
 p
we have
 φ (  p)  =  p − 1.
For a prime power
 p α
we have
φ (  pα )  =  pαpα  − 1  =  pα  − 1 (  p − 1)  =  pα 1 −
 1 p
=  pα
 p − 1 p
.

Euler’s totient function being multiplicative, we get

φ (n)  =  φ
 ω (n) ∏ i  = 1

piαi
=
 ω (n) ∏ i  = 1

piαi 1 −
 1 pi
=
n
 ω (n) ∏ i  = 1

1 −
 1 pi
=  n
 ω (n) ∏ i  = 1

 pi − 1 pi
,
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

 x̅φ (n)  :=  n − φ (n),
x̅φ (n)  :=
 n ∑ i  = 1(n, i )  ≠  1

1  =
 n ∑ i  = 1

[ (n, i ) ≠ 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

φ (n)  :=n  ⋅
 ∏ p∣np prime

1 −
 1 p
=  n  ⋅
 ω (n) ∏ i  = 1

1 −
 1 pi
,

with Dedekind psi function, which is defined by the formula

ψ (n)  :=n  ⋅
 ∏ p∣np prime

1 +
 1 p
=  n  ⋅
 ω (n) ∏ i  = 1

1 +
 1 pi
.

The totient function is multiplicative,[8] and accordingly A000010 has keyword:mult.

## Generating function

### Dirichlet generating function

The Dirichlet generating function of
 φ (n)
is
D{φ (n)}(s)  :=
 ∞ ∑ n  = 1

 φ (n) n  s
=
 ζ  (s − 1) ζ  (s)
=
 ζ  (2 s) (ζ  (s)) 2
⋅  D{ψ (n)}(s) .

## Harmonic series of totients

The harmonic series of totients (sum of reciprocals of the totients) diverges

 n ∑ i  = 1

 1 φ (i )
− A  (log n + B ) ∼ O
 log n n
O
 1 π (n)
,
where
 π (n)
is the prime counting function and (see A082695 for decimal expansion of
 A
)
A  =
 ∞ ∑ i  = 1

 q (i ) φ (i )
 1 i
=
 ζ  (2) ζ  (3) ζ  (6)
=  1.9435964368207592
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…
)
B  =  γ  −
 ∞ ∑ i  = 1

 q (i ) φ (i )
 log i i
=  0.57721566 − 0.60838171786  =  − 0.03116605
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

Φ (n)  :=
 n ∑ i  = 1

φ (i ), n ≥ 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

X̅Φ (n)  :=
 n ∑ i  = 1

x̅φ (i ), n ≥ 1,
where
 x̅φ (n)
is Euler’s cototient function.

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

 ψ (n) − φ (n) 2
=
 n 2
⋅  {
 ∏ p∣np prime

1 +
 1 p
−
 ∏ p∣np prime

1 −
 1 p
}.
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
ψ (n)  ⋅  φ (n)  =  n 2  ⋅
 ∏ p∣np prime

1 +
 1 p
1 −
 1 p
=  n 2  ⋅
 ∏ p∣np prime

1 −
 1 p 2
=
n 2  ⋅
 ∏ p∣np prime

 p 2 − 1 p 2
=
2 ⋅
 ∏ p∣np 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

 ψ (n) φ (n)
=
 ∏ p∣np prime

1 +
 1 p
1 −
 1 p
=
 ∏ p∣np prime

 p  + 1 p  − 1
.

## 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, ...}