1. ## Phi function help

The Euler Phi function counts the number of positive integers less than or equal to n, which are relatively prime to n.

Prove that if n is odd, then , and if n is even, then . I don't really know how to begin.

Here's my attempt to prove the first part, if n is odd, .

Let the prime decomposition of n be .

So,

But it seems like this would work for all n, not just odd n, so my above proof must be wrong.

2. Who tells thou that among the prime decomposition the p_i's are different from 2?
Instead decompose n>1 as n=2^m*p1^(a1)*...*pk^ak where m>=0

3. See result 2(b) here

4. Thank you guys for the reply. I think I got it now.

5. recall that $\varphi(ab)=\varphi(a)\varphi(b),$ whenever $\gcd(a,b)=1.$ now if $n$ is odd, then $\gcd(2,n)=1.$ so $\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n).$

if $n$ is even, then $n=2^km,$ for some $m, k \geq 1,$ with $\gcd(2,m)=1.$ therefore: $\varphi(2n)=\varphi(2^{k+1} m)=\varphi(2^{k+1}) \varphi(m)=$

$(2^{k+1} - 2^k)\varphi(m)=2(2^k - 2^{k-1})\varphi(m)=2\varphi(2^k)\varphi(m)=2\varphi(2^k m)=2\varphi(n). \ \ \ \square$