Euler Phi Function

Date: 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/