Trying solve the phi function again

[xWhiteyx]

This is getting on my nerves now. I am stumped on these:

Homework Statement

Obtain an expression for:
phi(p^3) and phi(P^n)

Homework Equations

phi(p^2)=p(p-1)

The Attempt at a Solution

The factors of P^n are 1 and P. Any number less than P^n that shares a factor must have p as a factor.

there are 3 numbers less than p^n. These are 1, P, and P^2.
Therefore phi(P^n)=P^n-3

But that is completely wrong, and I feel that I need lots of help. Also, if I can obtain an expression for phi(P^n) that might help me with phi(p^3).

 

[Dick]

There are lots of numbers less than p^n that are divisible by p. You can write them all as k*p where k<p^(n-1).

 

[xWhiteyx]

There are lots of numbers less than p^n that are divisible by p. You can write them all as k*p where k<p^(n-1).

But it asks us to obtain an expression in terms of p, without using additional numbers. If I could do that, then this homework would be easy but it isn't.
So far, i believe that this might get me somewhere:
Take 3^3 for example. Which numbers less than 27 share a factor with it?

Clearly 1 does, 2 doesn't, 3 does, 4 doesn't, 5 doesn't. Does 6? Are 6 and 27 coprime? No, since 6 factors as 2*3, and so shares a factor of 3 with 27, yet it is't a power of three.

But I don't know how to "obtain expression" for phi(P^3) or phi(p^n)

 

[Dick]

Here's a list of the numbers less than or equal to 3^3=27 that are NOT coprime to 27. 1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 7*3, 8*3, 9*3. Do you see a pattern? How many are there? I notice I've been counting 0 rather than 27 as one of them. My mistake.

 

[xWhiteyx]

Here's a list of the numbers less than 3^3=27 that are NOT coprime to 27. 0*3, 1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 7*3, 8*3. Do you see a pattern? How many are there?

9. So, the number of numbers coprime to, for example, 3^3 is 3^3- 3*3.

Would that then form the formula:
phi(P^n)=(P^n)-(P*P)

If that is the formula, then how would you express that?

 

[Dick]

9. So, the number of numbers coprime to, for example, 3^3 is 3^3- 3*3.

Would that then form the formula:
phi(P^n)=(P^n)-(P*P)

If that is the formula, then how would you express that?

I should have made the last number 9*3 rather than the first number 0*3, but the count is still 9. Yes, ok, so phi(27)=3^3-3^2. Before you jump to conclusions, what about phi(3^4)? The numbers not coprime to 3^4 are still 1*3, 2*3, 3*3, 4*3, ... 26*3, 27*3. Now how many are there? How about phi(3^5)?

 

[xWhiteyx]

I should have made the last number 9*3 rather than the first number 0*3, but the count is still 9. Yes, ok, so phi(27)=3^3-3^2. Before you jump to conclusions, what about phi(3^4)? The numbers not coprime to 3^4 are still 1*3, 2*3, 3*3, 4*3, ... 26*3, 27*3. Now how many are there? How about phi(3^5)?

phi(3^4)=54. 81-54=27 which is 3^3. So if I assume, before I find it out, that phi(3^5) would be 243-81 (162) and then figure it out.

The answer is indeed 162. So would phi(P^n)=(P^n)-(p^n-1)?

If so, how would you right that as an expression. My teacher said that it is all well and good spotting a pattern, but you need to be able to explain it.

 

[Dick]

Yes. phi(p^n)=p^n-p^(n-1). I thought that we have already been trying to explain it. As I said the numbers less than p^n that are NOT relatively prime to p^n are 1*p, 2*p, 3*p, ... p^(n-1)*p. You can just count them. How many are there? Doesn't that look like an explanation to you?

 

[xWhiteyx]

Yes. phi(p^n)=p^n-p^(n-1). I thought that we have already been trying to explain it. As I said the numbers less than p^n that are NOT relatively prime to p^n are 1*p, 2*p, 3*p, ... p^(n-1)*p. You can just count them. How many are there? Doesn't that look like an explanation to you?

Sorry, I'll try to be more clear. I'll show you what I mean by giving you my answer from an earlier quiestion question.

1) when p is a prime number, ontain an expression for phi(p) in terms of p:-

Numbers which arn't coprime to p would be divisible by p. All intergers from 1 to p-1 are not divisible by p. So the number of numbers less than p which are coprime to it is p-1.

That's the kind of expression I need. For P^3 and P^n

 

[Dick]

You can find the number of integers less than or equal to p^n which ARE coprime to p^n by finding the number of integers less than or equal to p^n which ARE NOT coprime to p^n, and then subtracting that from p^n. All of the integers less that or equal to p^n ARE coprime to p^n EXCEPT for the ones of the form k*p where k=1,2,3,4,...p^(n-1). I'm not sure I know how to say that more simply.

 

[xWhiteyx]

You can find the number of integers less than or equal to p^n which ARE coprime to p^n by finding the number of integers less than or equal to p^n which ARE NOT coprime to p^n, and then subtracting that from p^n. All of the integers less that or equal to p^n ARE coprime to p^n EXCEPT for the ones of the form k*p where k=1,2,3,4,...p^(n-1). I'm not sure I know how to say that more simply.

Could you then say that for P^3, it's basically the same thing, except excahnge P^n for P^3.

 

[Dick]

Could you then say that for P^3, it's basically the same thing, except excahnge P^n for P^3.

It's the same thing no matter what n is. phi(p)=phi(p^1)=p^1-p^0=p-1 works too.

 

[xWhiteyx]

thanks. I'll probably be getting back to you later on harder phi functions. This is still the easy bit.