42
$\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$
3
  • 3
    $\begingroup$ proofwiki.org/wiki/… $\endgroup$ Mar 7, 2014 at 3:24
  • 2
    $\begingroup$ It seems like your proof is 99% finished already :) $\endgroup$
    – Niklas B.
    Mar 7, 2014 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$ Mar 9, 2014 at 16:53

8 Answers 8

86
$\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$
4
  • 11
    $\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$ Mar 7, 2014 at 3:06
  • 7
    $\begingroup$ This is a very nice proof. $\endgroup$
    – Pedro
    Mar 7, 2014 at 3:06
  • 6
    $\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$ Mar 7, 2014 at 3:07
  • 3
    $\begingroup$ such a short, elegant and satisfying proof.. many Thanks!! $\endgroup$ Aug 31, 2017 at 8:31
27
$\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$
19
$\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$
6
$\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$
5
$\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$
1
  • $\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, 2014 at 4:30
5
$\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$
4
0
$\begingroup$

One very intuitive proof is to notice that $$\left(\frac n2 +k \right)+\left(\frac n2 -k \right)=n$$ So, if $d$ divdes $n$, then $d$ divides both or none of $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$. So, either there is at least one $d$ which divides all of $n$, $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$, or there is no such $d$.

This means either both or none of $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$ are coprime to $n$.

Note that we don't even need $\frac n2$ to be an integer. All we need are to have $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$ to be integers.

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