Formula for phi(n)

Date: 05/09/2003 at 11:36:49
From: Jay Brandon
Subject: Phi Function

I am investigating the phi function and am stuck at one point.

Ultimately my aim is to get a formula for phi(n) where n is any 
positive integer. I would appreciate it if you could explain in 
detail how you get from the above to the phi(n) formula, and any 
proofs that would help me understand along the way.

phi((m^p)(n^q))=((m^p)-(m^(p-1))((n^q)-(n^(q-1)), where p and q are 
positive integers and m and n are prime numbers. I have also applied 
this from the solution to phi(p^n) where p is a prime number and n is 
a positive integer.

Date: 05/09/2003 at 12:46:50
From: Doctor Luis
Subject: Re: Phi Function

Hi Jay,

You pretty much have it. You know, from the Fundamental Theorem of 
Arithmetic, that any number n can be decomposed into prime factors 
(suppose it has k unique prime factors):

  n = (p_1 ^ r_1) * (p_2 ^ r_2) * ... * (p_k ^ r_k)

where all the r_j > 0.

You also know that phi(n) is multiplicative, that is, for m,n
relatively prime, you have phi(m*n) = phi(m)*phi(n)

Applying this property of phi to phi(n), you get

  phi(n) = phi(p_1 ^ r_1) * phi(p_2 ^ r_2) * ... * phi(p_k ^ r_k)

You have already worked out the formula for phi(p^r)

  phi(p^r) = (p^r - p^(r-1)) = p^r(1 - 1/p)

Therefore,

  phi(n) = (p_1^r_1)(1-1/p_1) * ... * (p_k^r_k)(1-1/p_k)

         = (p_1^r_1 * ... * p_k^r_k) * ((1-1/p_1) * ... * (1-1/p_k))

  phi(n) = n * (1 - 1/p_1)*(1 - 1/p_2)*...*(1 - 1/p_k)

So there you have it. A formula for phi(n). You just have to know how 
many prime divisors it has.

You can find out more about phi(n), also known as the Totient 
Function, or Euler's Phi Function, in Eric Weisstein's World of 
Mathematics:

   Totient Function
   http://mathworld.wolfram.com/TotientFunction.html 

I hope this helped. Let us know if you have any more questions.

- Doctor Luis, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/09/2003 at 15:01:42
From: Jay Brandon
Subject: Phi Function

Can you go through why...

(p^r - p^(r-1)) = p^r(1 - 1/p)

I would really appreciate a step-by-step method.

Thanks in advance.

Date: 05/09/2003 at 15:10:41
From: Doctor Luis
Subject: Re: Phi Function

Hi Jay,

I'll start from the right side of the equation:

  p^r * (1 - 1/p) = p^r - (p^r / p)
                  = p^r - (p^r / p^1)
                  = p^r - p^(r-1)

Is it pretty clear now?

Alternatively, you could start from the left side,

  p^r - p^(r-1) = p^r * 1 - p^r * p^(-1)
                = p^r * (1 - p^(-1))
                = p^r (1 - 1/p)

Does this help?

Feel free to ask more questions about this problem or anything else.

- Doctor Luis, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/10/2003 at 11:30:49
From: Jay Brandon
Subject: Thank you (Phi Function)

I would like to thank all the doctors who have really been an 
inspiration to me and do hope that they continue the great job that 
they do. I am indebted to you guys. Once again, many thanks.