Results 1 to 5 of 5

Math Help - Phi Function

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    Phi Function

    Hi everyone,

    So i have the following question....

    Determine all integers n for which φ(n) is a divisor of n.

    Thinking about it logically, I think that the answer is going to be all the powers of 2?

    I cant really work out how to set this in some kind of proof/definitive form?

    Any ideas?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Nehushtan's Avatar
    Joined
    Mar 2013
    From
    Europe
    Posts
    42
    Thanks
    12

    Re: Phi function

    Well, \varphi(6)=2 divides 6, so there are also solutions other than powers of 2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    United States
    Posts
    16
    Thanks
    1

    Re: Phi Function

    I know phi(m) has m - 1 relative primes if 'm' is prime, but thats the only pattern I saw. Hope that helps.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2013
    From
    Home
    Posts
    18
    Thanks
    2

    Re: Phi Function

    A way to prove that \phi (2^n) | 2^n is by using the following property of the Euler function :

    \phi (p^k) = p^k (1-\frac{1}{p})

    for all primes p and where k>1.
    Now note that 2 is prime, so that

    \phi (2^n) = 2^n (1-\frac{1}{2}) = 2^{n-1}.
    This number is a divisor of 2^n.

    I don't know yet how to find other numbers satisfying that property...

    EDIT:
    You can use the identity

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

    If the only prime divisor of n is 2, then clearly \phi(n) = n/2 which is a divisor of n.
    Similarly, if the prime divisors of n are just 2 and 3, so n=2^k 3^l where k is nonzero, then
    \phi(n)=n\cdot \frac{1}{2}\cdot \frac{2}{3} = n/3.

    This argument does not seem to work when using other primes, but I'm not sure
    Last edited by Lockdown; March 8th 2013 at 12:55 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2013
    From
    Home
    Posts
    18
    Thanks
    2

    Re: Phi Function

    Ah, I've almost figured it out.
    Let's try and prove it:

    \phi (n) |n \Leftrightarrow n=2^a 3^b with a\geq 1 , b\geq 0.

    The implication from right to left is easy: I've sort of shown it above already.

    For the other implication, note that \phi(n) is even for n>2.
    Hence, since \phi(n) | n, n must be even, so write n=2^a R where R\geq 1 is odd.

    Now note \phi(n) = 2^{a-1} \phi(R) using multiplicativity of \phi. Hence we have

    2^{a-1} \phi(R) | 2^a R \Leftrightarrow \phi(R)|2R.

    Write R as product of primes
    R = p_1^{k_1} \cdots p_r^{k_r}. Then we have
    p_1^{k_1-1}(p_1-1) \cdots p_r^{k_r} | 2p_1^{k_1}\cdots p_r^{k_r}

    Hence
    (p_1-1)(p_2-1)...(p_r-1)|2p_1 p_2 \cdots  p_r.

    Now assume that r=1 to find
    p_1-1 | 2p_1. This implies p_1 = 3 and thus n=2^a 3^b for some b greater than or equal to zero.

    I'm not sure why we have that r=1. This remains to be proven, but I'm pretty sure this is the idea.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 20
    Last Post: November 27th 2012, 05:28 AM
  2. Replies: 3
    Last Post: November 29th 2011, 02:08 PM
  3. Replies: 0
    Last Post: October 19th 2011, 04:49 AM
  4. Replies: 4
    Last Post: October 27th 2010, 05:41 AM
  5. Replies: 3
    Last Post: September 14th 2010, 02:46 PM

Search Tags


/mathhelpforum @mathhelpforum