elem#theo - phi and odd #

Printable View

December 2nd 2008, 03:23 PM
cassiopeia1289

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?
December 2nd 2008, 05:15 PM
o_O

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)$
December 2nd 2008, 05:37 PM
cassiopeia1289

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?
December 2nd 2008, 05:49 PM
o_O

Quote:

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.
December 2nd 2008, 06:45 PM
cassiopeia1289

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?