Results 1 to 5 of 5

Thread: 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
    6

    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...

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

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

    Now if $\displaystyle b|a$ then...

    $\displaystyle 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

    $\displaystyle \chi$ $\displaystyle \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; Nov 26th 2011 at 10: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 $\displaystyle a$ and $\displaystyle b$. As for the rest, note that any prime $\displaystyle q$ (from that product in the formula for $\displaystyle k=\frac{\varphi(a)}{\varphi(b)}$) actually divides $\displaystyle \frac{a}{b}$.


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

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

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

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

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

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: Jun 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01: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: Apr 14th 2008, 04:07 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum