32
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ proofwiki.org/wiki/… $\endgroup$ – lab bhattacharjee Mar 7 '14 at 3:24
  • 2
    $\begingroup$ It seems like your proof is 99% finished already :) $\endgroup$ – Niklas B. Mar 7 '14 at 4:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Rodney Coleman Mar 9 '14 at 16:53
62
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ +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$... $\endgroup$ – Steven Stadnicki Mar 7 '14 at 3:06
  • 5
    $\begingroup$ This is a very nice proof. $\endgroup$ – Pedro Tamaroff Mar 7 '14 at 3:06
  • 3
    $\begingroup$ @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... $\endgroup$ – ShreevatsaR Mar 7 '14 at 3:07
  • $\begingroup$ such a short, elegant and satisfying proof.. many Thanks!! $\endgroup$ – Bibekpandey Aug 31 '17 at 8:31
19
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – hardmath Aug 20 '14 at 4:30
2
$\begingroup$

$\varphi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$ where $p_i$'s are prime factors of $n$. Finally in numerator part every term of $(1-\frac{1}{p_i})$ is even, and all the pis in denominator will be cancelled by $n$ in numerator. So it is even.

$\endgroup$
1
$\begingroup$

I saw a proof related to group theory in the answers. I would like to comment on it since I have a related idea but I cannot due to my low reputation. His proof is a little bit advance and I could not understand it well as I am new to the field.

However, I came with my own proof:

From group Theory, let $Z_n$ be the group modulo n under addition. Then, every co-prime-to-n element in this group is paired with its inverse which is a co-prime as well[i.e. they have the same order = n]. Thus, the number of co-primes divisible by 2 as required.

I am not sure if this proof works well, but seems to have a good idea.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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