Results 1 to 5 of 5

Math Help - 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 \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 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,407
    What do you know about Euler's phi function so far? Can you use the fact that \varphi (n) is multiplicative? Since \gcd (2, n) = 1, then \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 n=p_{1}^{k_{1}}p_{2}^{k_{2}} ... p_{r}^{k_{r}} where p_{1} is greater than 2 for some int. k.
    Now \phi(n) = (p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})
    Consider \phi(2n). Since n is odd and therefore does not have 2 as a factor, gcd(2,n)=1. Therefore:
    \phi(2n) = \phi(2)\phi(n)
    =\phi(2)(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})
    = 1(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})
    = \phi(n)
    So \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,407
    Consider \phi(2n). Since n is odd and therefore does not have 2 as a factor, gcd(2,n)=1. Therefore:
    \phi(2n) = \phi(2)\phi(n)
    But you're done here! This is what you wanted to prove since you know \color{red} \varphi (2) = 1
    =\phi(2)(p_{1}^{k_{1}} - p_{1}^{k_{1}-1}) ... (p_{r}^{k_{r}} - p_{r}^{k_{r}-1})
    Representing 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 \varphi (n) is multiplicative, then just simply saying \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: October 23rd 2008, 05:04 PM
  2. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 9th 2008, 03:23 PM
  3. elem.num.theo - GCD
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 9th 2008, 02:23 PM
  4. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 07:18 AM
  5. elem. # theo - gcd(a, a+n) divides n ...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 23rd 2008, 09:25 PM

Search Tags


/mathhelpforum @mathhelpforum