# Thread: elem#theo - phi and odd #

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

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

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

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

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?