Euler Phi FunctionDate: 02/24/2002 at 11:57:52 From: Rachel Harris Subject: Euler Phi Function For a coursework I have been asked to investigate the phi function; I have managed to work out a formula for when the number is prime, and I know how to work out the phi function of a number. As part of the coursework I have been asked to investigate: If p and q are prime investigate: phi(p^n * q^m) I know that this should work out with a formula, but I cannot find it and need to prove it. Date: 02/24/2002 at 14:00:37 From: Doctor Jubal Subject: Re: Euler Phi Function Hi Rachel, Thanks for writing Dr. Math. For your exploration of phi(p^n * q^m), let me show you a simpler but related problem that will help you analyze the one you're looking at. I'm going to examine phi(p^n). First, there are p^n - 1 numbers less than p^n, so p^n - 1 is an upper bound on phi(p^n). What we need to do now is figure out how many of thosenumbers share a common prime factor with p^n, and subtract those to get the actual value of phi(p^n). p^n has only one prime factor, p, so what we really need to do is figure out how many of the numbers less than p^n are divisible by p. Well, half of the positive integers are even, a third of them are divisble by 3, and in general 1/p of them are divisible by p, so from 1 to p^n, there must be (p^n)/p = p^(n-1) numbers divisible by p. However, we're only counting numbers less than p^n, so we have to throw out p^n itself, which leaves us with p^(n-1) - 1 numbers less than p^n that are divisible by p. Back to the phi function. There are p^n - 1 numbers less than p^n. p^(n-1) - 1 of them are divisible by p. The rest of them are coprime to p, so phi(p^n) = [p^n - 1] - [p^(n-1) - 1] = p^n - p^(n-1) = (p^n)(1 - 1/p) You can apply the same general approach to the problem you're working on - first find how many numbers are less than p^n * q^m; now figure out how many of those are divisible by p and/or q. Then, subtract those two quantities, and you have the number of numbers less than p^n * q^m that are coprime to p^n * q^m. Does this help? Write back if you'd like to talk about this more, or if you have any other questions. - Doctor Jubal, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/