# Thread: elem#theo - phi and odd #

1. ## 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?

2. 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)$

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

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

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