Results 1 to 3 of 3

Math Help - Another proof using the phi-function

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    5

    Another proof using the phi-function

    Prove the following:

    1.Φ(n^k)= n^(k-1)Φ(n)

    2.Φ(Φ(p^n))=p^(n-2)Φ((p-1)^2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    phi(n) = (n)product(1-1/pj) for j = 1,......,m

    phi(n^k) = (n^k)product(1-1/pj) for j = 1,.......,m (look through the def. of phi(n) to see why

    phi(n^k) = n^(k-1)((n)product(1-1/pj))

    phi(n^k) = (n^k-1)phi(n)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    If I'm not mistaken, all you have to do is:

    \phi(n^k) = n^k \prod_{p|n} \left(1 - \frac{1}{p}\right)

    We know that:

    \phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)

    So, with a little manipulation, we get:

    \phi(n^k) = n^{k-1}\left(n\prod_{p|n} \left(1 - \frac{1}{p}\right)\right)

    And this turns out to be:

    \phi(n^k) = n^{k-1}\phi(n)

    For the second one, note that:

    \phi(p^n) = p^n - p^{n-1} = p^{n-1}(p - 1)

    Now, if we call the above answer m, we can see that p|m and we get:

    \phi(m) = m\left(1 - \frac{1}{p}\right)

    \phi(m) = p^{n-2}(p-1)^2

    But I'm not sure this is right, since you put \phi((p-1)^2)... So, hopefully this just gets you thinking.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof that binomial function is a probability function?
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: December 28th 2011, 02:26 PM
  2. Replies: 1
    Last Post: December 30th 2010, 04:23 PM
  3. Function proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2009, 10:08 AM
  4. Replies: 0
    Last Post: September 14th 2009, 07:13 AM
  5. Function Proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 10th 2008, 08:00 AM

Search Tags


/mathhelpforum @mathhelpforum