What do you know about Euler's phi function so far? Can you use the fact that is multiplicative? Since , then
If n is an odd integer, show that .
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 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?
Representing 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 is multiplicative, then just simply saying is enough.Consider . Since n is odd and therefore does not have 2 as a factor, gcd(2,n)=1. Therefore:
But you're done here! This is what you wanted to prove since you know