Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Factors, Coprimes, and Totient Function > Totient Function

Euler's Totient Function

Definition

φ(n) is the number of positive integers not larger than n that are coprime to n.  (Coprime is defined this way: two numbers are coprime when they share no factor other than 1.)  Note that φ(1)=1, because 1 is coprime to itself.

Working with the Totient Function

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

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

Totient is a multiplicative function -- that means when a and b are coprime (i.e. GCD(a,b)=1), then φ(ab) = φ(a) φ(b). 

Mathworld says that by convention, φ(0) is defined as 1, even though there are no of positive integers that are not larger than 0, so by the definition, φ(0) really should be 0.  Moreover, Mathematica defines EulerPhi[0]=0 to be consistent with FactorInteger[0]

Together, these rules give the following formula for the totient of any number, given its prime factorization:

Let x = p1e1 p2e2 ... pnen 

φ(x) = p1e1-1 (p1-1) p2e2-1 ( p2-1)...pnen-1 ( pn-1)

Note that pe-1 (p-1) = pe (1-1/p).  Using this fact, the formula for φ(x) can be re-written as follows:

φ(x) = p1e1 (1-1/p1) p2e2 ( 1-1/p2)...pnen ( 1-1/pn)

and then by pulling out the factors p1e1 p2e2 ... pnen , which together equal x, we get the simplest formula:

φ(x) = x (1-1/p1) ( 1-1/ p2)...( 1-1/ pn)

Example

17640 = 23 32 5 72 

φ(17640) = 22 (2-1) 31 (3-1) 50 (5-1) 71 (7-1) = 4032

φ(17640) = 17640 (1/2)(2/3)(4/5)(6/7) = 4032

Additional facts: 

Mathworld says φ(n2) = nφ(n), but this can be generalized further: φ(nk) = nk-1φ(n)

The Sum of Totients of Divisors of n is n

In addition, Mathworld provides this factoid, from Euclid:

Σ φ(d) = n
d|n

Proof:

We will prove this sum-of-totients-of-divisors theorem by partitioning the set {1,2,3,...,n} into subsets according to each element's greatest common divisor with n.  Each subset of {1,2,3,...,n} will be called Q(g), the set of all integers between 1 and n inclusive, such that gcd(x,n) = g.  The Q(g) sets don't overlap, and their union is {1,2,3,...,n}, so the sum of the cardinality of the Q(g) sets is n.  Also, there is a one-to-one correspondence between the elements of Q(g) and the "proper coprimes" of n/g, which completes the proof.

For example, if n=12, then the set {1,2,3,4,5,6,7,8,9,10,11,12} is partitioned into these sets:

Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}

(All other Q(g) are empty sets)

These "Q" sets have the following three properties:

Q(g) is nonempty if and only if g divides n.  (If g weren't a divisor of n, then it could never be the greatest common divisor of n and some other number).

If x belongs to Q(g) for a given g, then it can't belong to another Q(h) where h≠g, because it wouldn't be possible for gcd(x,n)=g and gcd(x,n)=h.

For all x between 1 and n inclusive, there exists a g such that gcd(x,n) = g

Put together, these three properties imply that the union of all the Q(g) sets (for each g a divisor of n), which are pairwise mutually exclusive, is the set {1,2,3,...,n}.  And therefore, the sum of the cardinalities of each Q(g) equals n.

Now consider the set Q(g)/g, which is the set obtained by dividing each element of Q(g) by g.  You know all the elements of Q(g)/g are integers, because g is a divisor of every element of Q(g).  Let's look at our example, where n=12, again:

Q(1) = {1,5,7,11}  
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}

Q(1)/1 = {1,5,7,11}
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}

Now we will show that Q(g)/g is the set of "proper coprimes" of n/g.  By "proper coprimes" I mean positive numbers coprime to n that don't exceed n.  Keep in mind that the set of proper coprimes of n/g contains φ(n/g) elements, so by showing that Q(g)/g is the set of proper coprimes of n/g, we will show that |Q(g)|  = φ(n/g).  Also, since the set {n/g | g divides n} is equal to the set {d | d divides n}, and the union of the Q(g) sets is {1,2,3,...,n}, the result will follow, and the proof will be complete.

Suppose x is an element of Q(g)/g.  That means gx is an element of Q(g), so gcd(gx,n)=g, so gcd(x,n/g)=1, which means x is a coprime of n/g.  gx does not exceed n, so x does not exceed n/g, which means x is a proper coprime of n/g.

Now suppose x is a proper coprime of n/g.  gcd(x,n/g)=1, so gcd(gx,n)=g, so x is an element of Q(g)/g.

Therefore, |Q(g)| = φ(n/g).  The proof is complete.

Now, let's take one more look at our example, filling in the part about φ(n/g):

Q(1) = {1,5,7,11}  
Q(2)  = {2,10}
Q(3)  = {3,9}
Q(4)  = {4,8}
Q(6)  = {6}
Q(12)  = {12}

Q(1)/1 = {1,5,7,11}  
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}

φ(12/1)  = φ(12)  = 4
φ(12/2)  = φ(6)  = 2
φ(12/3)  = φ(4)  = 2
φ(12/4)  = φ(3)  = 2
φ(12/6)  = φ(2)  = 1
φ(12/12)  = φ(1)  = 1
Union of Q(g):
{1,2,3,...,12}
Sum of φ(d): 12

Internet references

Proof of: For any integer n, the sum of the totient values of each of its divisors equals n.

Related Pages in this website

Squares.

Fermat's Theorems -- Fermat's Little Theorem, in particular.

Euler's Totient Theorem -- a generalization of Fermat's Little Theorem

Number theory theorems, page 4: Totient.

Group - definition of a "group", which has properties closure, associativity, identity, and inverse.

The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.

A bunch of Ring Theory theorems and definitions.

Proof that there is no solution to the Diophantine equation A4+B4=C2, which means Fermat's last theorem is true 

Highly Composite Numbers -- numbers, n, such that no number smaller than n has as many factors as n.

 


The webmaster and author of this Math Help site is Graeme McRae.