Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to prove why $\phi(n)$ is even for $n>3$.

So far I am attempting to split this into 2 cases.

Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will always be even.

Case 2: $n$ is not a power of $2$. This is where I am unsure where to go. I figure I will end up using the fact that $\phi(n)$ is multiplicative, and I think I'll get a $(p-1)$ somewhere in the resulting product which will make the whole thing positive, as $p$ is prime implies $(p-1)$ is even.

share|improve this question
2  
2  
It seems like your proof is 99% finished already :) –  Niklas B. Mar 7 at 4:05
1  
It is not difficult to show that $\phi (n)$ is even for $n\geq 3$ so the image of $\phi$ is composed of $1$ and even numbers. However, not all even numbers are in the image. It is interesting to explore just what even numbers are in this set. –  Rodney Coleman Mar 9 at 16:53

5 Answers 5

up vote 27 down vote accepted

You can do it via the formula as you do, but you can also simply use the definition that $\phi(n)$ is the number of numbers $k$, with $1 \le k \le n$, such that $\gcd(n, k) = 1$.

Clearly, if $\gcd(k, n) = 1$, then $\gcd(n - k, n) = 1$ as well, so (for $n > 2$) all the numbers relatively prime to $n$ can be matched up into pairs $\{k, n-k\}$. So $\phi(n)$ is even.

share|improve this answer
2  
+1 for a fine 'first principles' proof - though I would note that for the one 'degenerate-pair' case where $k=n-k$, of course $\gcd(k, n)\neq 1$... –  Steven Stadnicki Mar 7 at 3:06
1  
This is a very nice proof. –  Pedro Tamaroff Mar 7 at 3:06
    
@StevenStadnicki: Yes, that's why I wrote "(for $n > 2$)", as $k = n - k$ and $\gcd(k, n) = 1$ can happen when $n = 2$ and $k = 1$. :-) For larger $n$ though, $k = n - k$ means that $n = 2k$ and $\gcd(n, k) = \gcd(2k, k) = k > 1$. You're right that it's worth noting explicitly... –  ShreevatsaR Mar 7 at 3:07

Suppose $n>3$. If $n$ has an odd prime factor, say $p$; then $n=p^km,(m,p)=1$ and $\varphi (n)=\varphi(p^k)\varphi(m)=(p-1)p^{k-1}\varphi(m)$, with $p-1$ even. If $n$ has no odd prime factors, then $n=2^k$ with $k>1$ so $\varphi(2^k)=2^{k-1}$ is even.

share|improve this answer

Hint $\ $ The map $\,x\mapsto -x\pmod n\,$ has no fixed points so pairs-up the residues coprime to $n.\,$

Remark $\ $ Such use of reflections (or involutions) to pair-up terms frequently proves handy, e.g. see prior posts here on Wilson's theorem (in groups), esp. this one to start.

share|improve this answer

This answer will use some slightly more advanced machinery to get a short answer.

If $n\geq 3$ (you don't need to assume $n > 3$) then $-1\neq 1$ in $\mathbb{Z}/n\mathbb{Z}$, but $(-1)^2 = 1$, so $-1$ is an element of order $2$ in $(\mathbb{Z}/n\mathbb{Z})^{\times}$, which means that $|(\mathbb{Z}/n\mathbb{Z})^{\times}| = \varphi(n)$ is even by Lagrange.

share|improve this answer

A proof using group theory: Let $Z_n$ denote the cyclic group of order $n$. There exists a nontrivial order 2 element of $Aut(Z_n)$ for all $n>2$, namely the (additive) inversion map. Since $|Aut(Z_n)|=\phi(n)$, this implies that $\phi(n)$ is even for all $n>2$.

share|improve this answer
    
Inversion map might be clarified to mean mapping to an additive inverse. This previous Math.SE Question would be worth adding as a link for the proposition about $Aut(Z_n)$. –  hardmath Aug 20 at 4:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.