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 .
But it seems like this would work for all n, not just odd n, so my above proof must be wrong.