Thread: 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.

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

See result 2(b) here

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

recall that whenever now if is odd, then so

if is even, then for some with therefore: