Results 1 to 2 of 2

Math Help - Euler Phi function

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Euler Phi function

    Find all n such that phi(n) = 6. Prove there are no more.

    I know phi(7), phi(9), phi(14), phi(18) = 6 and those are the only ones. However, I don't know how to show there are no others. Any advice is appreciated... Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    757

    Re: Euler Phi function

    factor n into distinct prime powers. since φ(p^k) = (p -1)(p^(k-1)) n cannot have a prime factor larger than 7.

    if n has 7 as a prime factor, it can only be a single power of 7, since 7 > 6 (if k > 1, k - 1 > 1, so 7^(k-1) > 7 > 6).

    if n has 5 as a prime factor, then φ(n) has (5-1)(5^(k-1)) = 4(5^(k-1)), so φ(n) has 4 as a factor, but 4 does not divide 6.

    if n has 3 as a prime factor, it could either be a single power or squared power of 3, if k > 2, φ(3^k) = (2)(3^(k-1)) > 6.

    if n has 2 as a prime factor, it could only be a single or double power of 2, because φ(8) = 4, and φ(16) = 8 > 6.

    so we already have it whittled down to:

    2
    2*2
    3
    3*3
    2*3
    2*2*3
    2*3*3
    2*2*3*3
    7
    2*7
    2*2*7
    3*7
    3*3*7
    2*3*7
    2*2*3*7
    2*3*3*7
    2*2*3*3*7

    one could check all these manually. however, note that if φ(n) = 6, and 7 divides n, then φ(n/7) = 1, since φ(7) = 6. that means that 7 and 14 are the only possibilities for n divisible by 7 (since φ(k) = 1 implies k =1 or 2). that takes the last 7 off the list.

    note that if 9 divides n, we have the same situation, which eliminates 36.

    if n is divisible by 3, but not by 9, then since φ(3) = 2, we need φ(n/3) = 3. but φ(k) = 3 has no solutions (can you prove this? it's not hard). this eliminates 6 and 12.

    φ(4) = 3, φ(3) = 2, and φ(2) = 1. none of these are 6.

    so 9,18,7,14 are the only possible solutions. and these are solutions, so that's it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's phi-function.
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 5th 2010, 10:37 AM
  2. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 05:10 AM
  3. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 04:33 AM
  4. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 07:42 PM
  5. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2009, 04:42 PM

Search Tags


/mathhelpforum @mathhelpforum