Results 1 to 5 of 5

Thread: elem#theo - phi and odd #

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    elem#theo - phi and odd #

    If n is an odd integer, show that $\displaystyle \phi(2n) = \phi(n)$.
    I know this is true, but I'm having difficulties showing that n is odd without getting into n=2k+1 troubles. I know that to make n even, you can have $\displaystyle n=2^kj$ for some gcd(2,j) = 1, that way all your 2s are separated, but other than that - how do you show its even?
    Should I write the prime factorization of n? where none equal 2?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,410
    Thanks
    1
    What do you know about Euler's phi function so far? Can you use the fact that $\displaystyle \varphi (n)$ is multiplicative? Since $\displaystyle \gcd (2, n) = 1$, then $\displaystyle \varphi (2n) = \varphi (2) \varphi (n) = \varphi (n)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok - here's what I did and lemme know if it works - please

    I let $\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}} ... p_{r}^{k_{r}}$ where $\displaystyle p_{1}$ is greater than 2 for some int. k.
    Now $\displaystyle \phi(n) = (p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})$
    Consider $\displaystyle \phi(2n)$. Since n is odd and therefore does not have 2 as a factor, gcd(2,n)=1. Therefore:
    $\displaystyle \phi(2n) = \phi(2)\phi(n)$
    $\displaystyle =\phi(2)(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})$
    $\displaystyle = 1(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})$
    $\displaystyle = \phi(n)$
    So $\displaystyle \phi(n) = \phi(2n)$ when n is odd.

    Does that work?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,410
    Thanks
    1
    Consider $\displaystyle \phi(2n)$. Since n is odd and therefore does not have 2 as a factor, gcd(2,n)=1. Therefore:
    $\displaystyle \phi(2n) = \phi(2)\phi(n)$
    But you're done here! This is what you wanted to prove since you know $\displaystyle \color{red} \varphi (2) = 1$
    $\displaystyle =\phi(2)(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})$
    Representing $\displaystyle n$ through its prime power decomposition doesn't really do anything and is not at all necessary. If you're allowed to use the fact that $\displaystyle \varphi (n)$ is multiplicative, then just simply saying $\displaystyle \varphi (2n) = \varphi (2) \varphi (n) = (1)\varphi (n)$ is enough.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    yeah but I think my prof wants more than that - that seems to easy to be a long proof

    is my way actually valid though?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elem#theo - induction + Bertrand's
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Oct 23rd 2008, 04:04 PM
  2. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Oct 9th 2008, 02:23 PM
  3. elem.num.theo - GCD
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Oct 9th 2008, 01:23 PM
  4. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 26th 2008, 06:18 AM
  5. elem. # theo - gcd(a, a+n) divides n ...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Sep 23rd 2008, 08:25 PM

Search Tags


/mathhelpforum @mathhelpforum