Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Totient function and divisibility

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1

    Totient function and divisibility

    The problem:
    Prove that if d divides n then \phi (d) divides \phi (n) .
    (I will presume that d and n are positive integers.) This is one of those "duh!" thoughts but I am messing up the proof somehow. I'd appreciate it is someone could take a look at it.

    First: If d|n then n = kd for some positive integer k. Using their decomposition into powers of primes, let
    d = 2^{a_2} \cdot 3^{a_3} \cdot 5^{a_5} \cdot \text{ ...}
    and
    k = 2^{b_2} \cdot 3^{b_3} \cdot 5^{b_5} \cdot \text{ ...}

    Then
    kd = 2^{a_2 + b_2} \cdot 3^{a_3 + b_3} \cdot 5^{a_5 + b_5} \cdot \text{ ...}

    Now, we have that
    \phi (d) = \left ( 2^{a_2 -1 } \right ) (2 - 1) \cdot \left ( 3^{a_3 -1 } \right ) (3 - 1) \cdot \left ( 5^{a_5 -1 } \right ) (5 - 1) \cdot \text{ ...}

    and
    \phi (kd) = \left ( 2^{a_2 + b_2 -1 } \right ) (2 - 1) \cdot \left ( 3^{a_3 + b_3 - 1 } \right ) (3 - 1) \cdot \left ( 5^{a_5 + b_5 - 1 } \right ) (5 - 1)\cdot \text{ ...}

    So finally we get
    \frac{ \phi (kd) }{ \phi (d) } = \left ( 2^{(a_2 + b_2 - 1) - (a_2 - 1)} \right )  \cdot \left ( 3^{(a_3 + b_3 - 1) - (a_3 - 1)} \right ) \cdot \text{ ...}

    \frac{ \phi (kd) }{ \phi (d) } = \left ( 2^{b_2} \right ) \cdot \left ( 3^{b_3} \right ) \cdot \left ( 5^{b_5} \right ) \cdot \text{ ...}

    or
    \frac{ \phi (kd) }{ \phi (d) } = k

    Now, I thought that simplified expression to be kinda cool. But as I was thinking about it I checked:
    \frac { \phi (3 \cdot 4) }{ \phi (3) } = \frac{4}{2} = 2 \neq k

    So I've done something incorrectly. (Though I suspect the general structure of the proof is sound.)

    Any thoughts?

    -Dan
    Last edited by topsquark; September 27th 2013 at 02:08 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Totient function and divisibility

    The formula \phi(p^k)=p^{k-1}(p-1) works only for k > 0.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1

    Re: Totient function and divisibility

    Quote Originally Posted by emakarov View Post
    The formula \phi(p^k)=p^{k-1}(p-1) works only for k > 0.
    Ah! So if a prime factor is missing...

    I'll be back.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1

    Re: Totient function and divisibility

    I think I've got the general idea, but I can't find a good way to express the final answer.

    Let
     \large d = \prod _i p_i ^{a_i}, where i runs over the primes in the decomposition.

    \large k = \prod _j p_j ^{b_j}, ditto

    \large kd = \prod _{i, j} p_i^{a_i} p_j ^{b_j} i and j run over the decompositions and have no restrictions
    (The above definitions solve the problem of having 0 exponenets.)

    Continuing we have
    \large \phi (d) = \phi \left ( \prod _i p_i ^{a_i} \right )

    and
    \large \phi (kd) = \phi \left ( \prod _{i, j} p_i^{a_i} p_j ^{b_j} \right )

    We need to have some care about primes common to both factor sets. So break the factors into two groups: primes common to both k and d (x), and not shared (y):

    \large \phi (kd) = \phi \left \[ \left ( \prod _x p_x^{c_x} \right )  \left ( \prod _y p_y ^{e_y} \right ) \right \]

    By construction the x product and y product are relatively prime, so we may factor:
    \large \phi (kd) = \phi \left ( \prod _x p_x^{c_x} \right ) \phi \left ( \prod _y p_y ^{e_y} \right )

    So this leaves us with
    \large \frac{\phi (kd) }{ \phi (d) } = \frac{ \phi \left ( \prod _x p_x ^{c_x} \right ) \phi \left ( \prod _y p_y ^{e_y} \right ) }{  \phi \left ( \prod _i p_i ^{a_i} \right ) }

    \large = \frac{ \prod_x p_x ^{c_x - 1} (p_x - 1 )\cdot \prod_y p_y ^{e_y - 1} (p_y - 1) }{ \prod_i p_i ^{a_i - 1}  ( p_i - 1) }

    Clearly the denominator is completely canceled by the factors in the numerator. But how do I show that? I'm a bit stumped on how to express this mathematically. (Perhaps because I need to get to bed!)

    -Dan

    PS Is this problem really this abstract (and long)? This is rather more intense than the other problems in the set.
    Last edited by topsquark; September 27th 2013 at 07:19 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1

    Re: Totient function and divisibility

    Success! All I needed to finish the proof came to me just after I woke up.

    If that sounds nerdy I woke up at 3 AM the other night working on one point compactification in my sleep.

    -Dan
    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: October 2nd 2011, 09:10 AM
  2. Totient Function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 28th 2011, 07:28 PM
  3. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 09:41 AM
  4. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 22nd 2009, 02:21 AM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum