GCD = 1

For any $k$ which is relatively prime to $n,$ we have $n-k$ also relatively prime to $n.$ This means that the number of relatively prime numbers to $n$ that are less than $n$ must be even, since we can group them into ( $k,n-k$ ) pairs.

Remark: Of course, if $k=n-k,$ this wouldn't be a pair. But if $k=n-k,$ then $n=2k$ but then $k$ would not be relatively prime to $n.$ This is precisely why we must exclude $n=2.$

We have that Euler's totient function, $\varphi(n)$ , calculates the number of numbers less than n which are coprime to $n$ . We have the property that if $n = p^k$ for some prime p, then $\varphi(n) = \varphi(p^k) = p^k - p^{k - 1}$ . As we have here, let $k = 1$ . Then we get that the answer will take the form $p - 1$ . Since for $n > 2$ , $p$ must be an odd number. Thus $p - 1$ must be even.

The number of positive integers less than $n$ that are relative prime to $n$ is $\phi (n)$ , where $\phi : \mathbb{Z^+}\rightarrow\mathbb{Z^+}$ is Euler's Totient Function . It's known that

$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$ where $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ .

With some manipulations:

$\phi(n)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \cdot (1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$

$\phi(n)=p_1^{\alpha_1}(1-\frac{1}{p_1})p_2^{\alpha_2}(1-\frac{1}{p_2})\cdots p_k^{\alpha_k}(1-\frac{1}{p_k})$

$\phi(n)=(p_1^{\alpha_1}-p_1^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots (p_k^{\alpha_k}-p_k^{\alpha_k-1})$

Now, there are two options for $n$ :

• If $n\neq 2^m$ , there exists at least an odd prime factor in his factorization, let it be $p_h$ . Obviously, $p_h^{\alpha_h}$ and $p_h^{\alpha_h-1}$ are odd too. Therefore $p_h^{\alpha_h}-p_h^{\alpha_h-1}$ is even: $\phi(n)$ has an even factor, so it's even.

• If $n=2^m$ , $\phi(n)=2^m(1-\frac{1}{2})=2^{m-1}$ , which is even (for $m>1$ , or $n>2$ , which is a hypothesis).

In conclusion, $\phi(n)$ is even $\forall n>2$ .