Exercise 2.3.9 (For what values of $n$ is $\phi(n)$ odd?)

Proof. First solution.

If $n>1$, then $n$ as a prime factor $p$, and $n$ is divisible by $p^{\alpha }$, where $\alpha \ge 1$.

Then $\varphi (n)$ is divisible by $p^{\alpha }-p^{\alpha -1}=p^{\alpha -1}(p-1)$.

If $p$ is odd, then $2\mid p-1$, and $p-1\mid \varphi (n)$, so $\varphi (n)$ is even.

If $p=2$, then $2^{\alpha }-2^{\alpha -1}=2^{\alpha -1}$ divides $\varphi (n)$. If $\alpha \ge 2$, then $2\mid 2^{\alpha -1}$ and $2^{\alpha -1}\mid \varphi (n)$, so $\varphi (n)$ is even.

It remains only $n=1$ or $n=2$, for which $\varphi (n)=1$ is odd.

To conclude, $\varphi (n)$ is odd only for the values $n=1$ or $n=2$.

Second solution.

Consider , for $n\ge 2$, the map

where ${(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$ is the group of invertible elements of $\mathbb{Z}∕\mathit{n\mathbb{Z}}$, whose order is $\varphi (n)$.

This makes sense, since $i\wedge n=1\Rightarrow (i-n)\wedge n=1$, thus $f({[i]}_n)\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$.

Since $i=n-(n-i)$, $f\circ f=1_{{(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}}$, so $f$ is an involution.

We search the fixed points of this involution. If $f({[i]}_n)={[i]}_n$, where ${[i]}_n\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$, then $i\equiv n-i(\mathit{mod}n)$, thus

• If $n$ is odd, then $i\equiv 0(\mathit{mod}n)$, so ${[i]}_n=0$ and then ${[i]}_n\notin {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$: this is a contradiction.
• If $n$ is even, $i\equiv 0(\mathit{mod}n∕2)$, thus $\gcd (i,n)=n∕2>1$ and then ${[i]}_n\notin {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$. Contradiction again.

Therefore $f$ is an involution without fixed point. We can partition ${(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$ in pairs $\{c,f(c)\}$ for $c\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$, where $f(c)\ne c$, thus

□