Results 1 to 5 of 5

Math Help - help to proof : if a|b then phi(a) | phi(b)

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    6

    help to proof : if a|b then phi(a) | phi(b)

    hello.
    can any one proof this problem for me please?
    if a|b then phi(a) | phi(b). (b is natural number).

    tanx.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: help to proof : if a|b then phi(a) | phi(b)

    Quote Originally Posted by mostafashaeri View Post
    hello.
    can any one proof this problem for me please?
    if a|b then phi(a) | phi(b). (b is natural number).

    tanx.
    By definition is...

    \varphi(a)= a\ \prod_{p|a} \frac{p-1}{p}

    \varphi(b)= b\ \prod_{p|b} \frac{p-1}{p} (1)

    Now if b|a then...

    k= \frac{a}{b}\ \prod_{q} \frac{q-1}{q} (2)

    ... where q belongs to the set of primes deviding a and not b, is a natural number...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    6

    Re: help to proof : if a|b then phi(a) | phi(b)

    thank.
    So?
    i don't understand why b|a?
    the problem say that a|b
    Last edited by mostafashaeri; November 26th 2011 at 11:31 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2011
    Posts
    6

    Re: help to proof : if a|b then phi(a) | phi(b)

    i don't understand why b|a . in the problem a|b but you said b|a.
    please explain how to continue this proof
    thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Re: help to proof : if a|b then phi(a) | phi(b)

    Quote Originally Posted by mostafashaeri View Post
    i don't understand why b|a . in the problem a|b but you said b|a.
    please explain how to continue this proof
    thanks
    I think he switched a and b. As for the rest, note that any prime q (from that product in the formula for k=\frac{\varphi(a)}{\varphi(b)}) actually divides \frac{a}{b}.


    Another proof (back to the original a|b ) :

    Let b = c\cdot d where c is the greatest integer dividing b such that \text{gcd}(c,a)=1.

    Adding to this that a|b , we have that d and a must share the exact same prime divisors (and a|d too) . Thus in fact, any number coprime to d is coprime to a and viceversa. It follows then that \varphi(a) | \varphi(d) (*).

    Finally since c and d are coprime, we have: \varphi(b) = \varphi(c)\cdot \varphi (d), and since \varphi(a) | \varphi(d) we are done.

    (*) In each set \{k\cdot a,..,k\cdot a +a-1\} for k = 0,...,\tfrac{d}{a}-1 we have exactly \varphi(a) numbers coprime to d. These sets form a partition of \{0,...,d-1\} so indeed \varphi(a)\cdot \tfrac{d}{a} = \varphi(d).
    Last edited by PaulRS; November 26th 2011 at 07:19 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 12:13 PM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum