For every positive integer n greater than $2$, $\phi(n)$ is an even integer.

Question

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer.

I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show me anyone know how or where to find it?

Answer 1

Note that if $x$ is relative prime to $n$, so is $n-x$ except for $n=2$, since you double count $x=1=2-1=n-x$.

Answer 2

One way to prove it is the following: When $n\geq 3$ we have that $-1\neq 1$ in $\mathbb{Z}/n\mathbb{Z}$, so $-1$ is an element of order $2$ in $(\mathbb{Z}/n\mathbb{Z})^*$ and the result follows by Lagrange since $\varphi(n)$ is the order of that group.

Answer 3

Let $n = p_1^{a_1} \cdot p_2^{a_2}\cdot \ldots \cdot p_k^{a_k}$. Then for $\phi(n)$ we have:

$$\phi(n) = p_1^{a_1}\left(\frac{p_1-1}{p_1}\right)\ldots$$ $$\phi(n) = p_1^{a_1 - 1}\cdot (p_1-1)\ldots$$

And since $\phi(n)$ is integer for every natural number $n$, for $p_1$ is odd, $(p_1 - 1)$ is even so $\phi(n)$ has 2 as a factor, i.e $\phi(n)$ is even number.

Now check the case when $n$ is a power of two, because every other number has at least one odd prime factor. Note that then $a_1 - 1 > 0$ and $p_1 = 2$ if $n$ is power of $2$. So $p_1^{a_1-1}$ is a even factor of $\phi(n)$, hence $\phi(n)$ is even number.

Answer 4

If $n$ has no odd prime divisor, then $n=2^r$, so that $\phi(n)=2^r-2^{r-1}$ is even for $r\ge 2$. Otherwise $n$ has an odd prime divisor $p$, which yields an even factor $p-1$ in the product formula for $$ \phi(n)=\frac{n}{\prod_{p\mid n}p}\prod_{p\mid n}(p-1). $$ This proof shows more: $2^s \mid \phi(n)$, not just $2\mid \phi(n)$, where $s$ is the number of odd prime divisors of $n$.

Answer 5

Lemma: If $\gcd(n,k)=1$ then $\gcd(n,n-k)=1$.

Proof: Suppose $d|n,d|n-k$ so $d|n-(n-k)$ and $d|k$. So we have $d|k$ and $d|n$ and according to the first part, $d=1$. Thus, $\gcd(n,n-k)=1$.
This means you count each $k$ that $\gcd(n,k)=1$ twice.