1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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