Euler Totient Function Calculator


Euler Phi Function Calculator
n =

In number theory, the Euler Phi Function or Euler Totient Function φ(n) gives the number of positive integers less than n that are relatively prime to n, i.e., numbers that do not share any common factors with n. For example, φ(12) = 4, since the four numbers 1, 5, 7, and 11 are relatively prime to 12.

For small integers, it may be easy to simply enumerate and count the number of relatively prime integers less than n. But for larger numbers, it is more convenient to use the explicit formula

φ(n) = nΠ(1 - 1/pj),

where the pj's are the prime factors of n. For example, the prime factors of 12 are 2 and 3. If we use the product formula above to compute φ(12), we get

φ(12) = 12Π(1 - 1/pj)

= 12(1 - 1/2)(1 - 1/3)

= 12(1/2)(2/3)

= 4.

Properties of φ(n)

If p is prime then φ(p) = p-1.

If m and n are relatively prime integers (GCD(m,n) = 1) then φ(mn) = φ(m)φ(n). For instance, we can use this property to compute φ(210). Since 210 = 15*14 and 15 and 14 are relatively prime to one another, then

φ(210) = φ(15*14) = φ(15)φ(14)

= [15Π(1 - 1/pj)]*[14Π(1 - 1/pj)]

= [15(1 - 1/3)(1 - 1/5)]*[14(1 - 1/2)(1 - 1/7)]

= 8*6

= 48

Identities

One of the most elegant properties of the phi function is

    n = Σ φ(d),

where the d ranges over the divisors of n. The Möbius Inversion formula gives the identities

    φ(n) = Σ μ(n/d)d = nΣ μ(d)/d,

where μ(n) is the Möbius Mu function. Other summation identities are

    n/φ(n) = Σ μ(d)²/φ(d) and

    nφ(n)/2 = Σ r,

where 0 < r < n and GCD(r,n) = 1. For example, when n = 12, we have

12φ(12)/2 = 24 = 1 + 5 + 7 + 11.

Three other identities are

    2Σ φ(k) = 1 + Σ μ(k)⌊n/k⌋² and

    Σ φ(k)/k = Σ μ(k)⌊n/k⌋/k

    Σ GCD(k,n) = nΣ φ(d)/d

where k = 1,...,n.

© Had2Know 2010