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.