Results 1 to 3 of 3

Math Help - totient function

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    3

    totient function

    Hey guys, I need some help here.

    a)Let n and a be positive integers and p be a prime. Show (p-1) | \varphi(n) and p^{a-1} | \varphi(n) given p^a | n.
    b) Using part a, find all positive integers n for \varphi(n) =12.

    a)
    Since p^a | n, this implies \varphi(p^a) | \varphi(n)
    And \varphi(p^a)=p^a-p^{a-1}=(p-1)p^{a-1}
    Thus (p-1) | \varphi(n) and p^{a-1} | \varphi(n).

    Is this good enough?

    b) I am stuck on this one.

    Thanks for your help.
    Last edited by fir2011; October 2nd 2011 at 06:32 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: totient function

    Part (a) looks good. I don't know how to do part (b).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: totient function

    for part (b) consider p^a|n.

    there are two cases: a = 1, in which case p = 2,3,5,7 or 13.

    a > 1, in which case p = 2 or 3.

    i will give something of the flavor of what you have to do. suppose 2^a|n. a can be at most 3, since 4 is the largest power of 2 that divides 12.

    if 8|n, then φ(n/8) = 12/φ(8) = 3. but there is no number k for which φ(k) = 3, so 8 does not divide n.

    if 4|n, then φ(n/4) = 12/φ(4) = 6. the numbers for which φ(k) = 6 are 7,9 and 14. 14 is divisible by 2, which would imply 8|n, contradiction.

    therefore, k can only be 7 or 9, leading to n = 28 or 36, both of which indeed have φ(n) = 12.

    if 3^a|n, then a = 1 or 2 (since 18 does not divide 12). suppose 9|n. then φ(n/9) = 12/φ(9) = 2. hence n/9 = 3,4,or 6.

    since 3,6 are divisible by 3, and 27 does not divide n, we must have n = 36 (which we have already accounted for).

    that leaves only products of primes to the first power as factors for n.

    i leave it to you to show that 13, 2*13, 3*7, and 2*3*7 are the only possibilities left.
    Last edited by Deveno; October 2nd 2011 at 12:44 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Totient Function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 28th 2011, 08:28 PM
  2. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 06:38 PM
  3. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 07:11 PM
  4. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 08:16 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 09:53 PM

Search Tags


/mathhelpforum @mathhelpforum