Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

if you have any other questions.

- Doctor Jubal, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search