Euler's Totient Function - OeisWiki

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]

Contents

• 1 Totatives and cototatives
• 2 Properties
• 3 Formulae
  • 3.1 Euler’s totient function
  • 3.2 Euler’s cototient function
  • 3.3 Euler’s totient function and Dedekind psi function
• 4 Generating function
  • 4.1 Dirichlet generating function
• 5 Harmonic series of totients
• 6 Related functions
  • 6.1 Iterated Euler totient function
  • 6.2 Iterated Euler cototient function
  • 6.3 Totient summatory function
  • 6.4 Cototient summatory function
  • 6.5 Half difference of Dedekind psi function and Euler’s totient function
  • 6.6 Product of the Dedekind psi function with Euler’s totient function
  • 6.7 Quotient of the Dedekind psi function by Euler’s totient function
• 7 Sequences
• 8 See also
• 9 Notes

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

Euler’s totient function is a multiplicative arithmetic function, e.g.

φ (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).

Iterated Euler cototient function

(...)

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  =  n rad (n)   2 ⋅     ∏  p∣np prime    (  p 2 − 1),

where

rad (n)

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

See also

• Peter Luschny, Sequences related to Euler’s totient function.
• Totient valence function
• Coprimality triangle
• Coprimality
• Totatives
• Totient summatory function
• Coprimorial or product of totatives of n
• Euler’s cototient function (number of cototatives of

  n

  )
• Noncoprimorial
• Dedekind ψ function

Notes

1. ↑ Harold M. Stark, An Introduction to Number Theory. Chicago: Markham Publishing Company (1970) p. 77.
2. ↑ R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective. New York: Springer (2001) p. 119.
3. ↑ H. E. Rose, A Course in Number Theory. Oxford: Clarendon Press (1988) p. 21.
4. ↑ D. N. Lehmer, “Dickson’s History of the Theory of Numbers” Bull. Amer. Math. Soc. 26 3 (1919), 128.
5. ↑ Stark, p. 78.
6. ↑ 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.
7. ↑ For the derivation of this formula see equations (1) to (12) of: Weisstein, Eric W., Totient Function, from MathWorld—A Wolfram Web Resource.
8. ↑ Stark, p. 83, Theorem 3.15.