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

[edit] 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

[edit]

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

[edit]

Euler’s totient function

[edit]

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

[edit]

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

[edit]

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

[edit]

Dirichlet generating function

[edit]

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

[edit]

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

[edit]

Iterated Euler totient function

[edit]

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

[edit]

(...)

Totient summatory function

[edit]

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

[edit]

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

[edit]

ψ (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

[edit]

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

[edit]

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

[edit]

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

[edit]

• 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

[edit]

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.