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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/