Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Trying solve the phi function again

  1. Jan 11, 2010 #1
    This is getting on my nerves now. I am stumped on these:
    1. The problem statement, all variables and given/known data
    Obtain an expression for:
    phi(p^3) and phi(P^n)


    2. Relevant equations
    phi(p^2)=p(p-1)

    3. 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).
     
  2. jcsd
  3. Jan 11, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  4. Jan 11, 2010 #3
    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)
     
  5. Jan 11, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Jan 11, 2010 #5
    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?
     
  7. Jan 11, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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)?
     
  8. Jan 11, 2010 #7
    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.
     
  9. Jan 11, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  10. Jan 11, 2010 #9
    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
     
  11. Jan 11, 2010 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Jan 11, 2010 #11
    Could you then say that for P^3, it's basically the same thing, except excahnge P^n for P^3.
     
  13. Jan 11, 2010 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's the same thing no matter what n is. phi(p)=phi(p^1)=p^1-p^0=p-1 works too.
     
  14. Jan 11, 2010 #13
    thanks. I'll probaly be getting back to you later on harder phi functions. This is still the easy bit.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook