Properties of the Phi FunctionDate: 01/19/99 at 14:06:27 From: Hugo Joyce Subject: The 'PHI' function. Dear Dr. Math, Could you inform me of any possible links between Phi of a number and the number? For example I know that Phi of any prime number p can be found by subtracting 1 from the number: Phi(p) = p - 1 We have also been given things like: Is phi(7*4) = phi(7)*phi(4) true or false? Thank you, Hugo Date: 01/19/99 at 14:38:41 From: Doctor Rob Subject: Re: The 'PHI' function. Thanks for writing to Ask Dr. Math! The things you need to know are: (1) phi(n) is the number of integers x with 0 < x <= n such that GCD(x,n) = 1. This implies that if n > 1, phi(n) < n. (2) If GCD(n,m) = 1, then phi(n*m) = phi(n)*phi(m). [This tells you that to compute phi(n) for any n, you need only be able to compute phi applied to prime powers.] (3) If p is prime and k >= 2, then phi(p^k) = p*phi(p^[k-1]). [This tells you that to compute phi applied to prime powers, you need only compute phi applied to primes.] (4) If p is prime, phi(p) = p - 1. [This is the last piece, telling you what phi(p) is.] - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/