Parity of Euler's totient function

Question

Let $S$ be a set of all numbers $k$ such that $(n, k) = 1, 1 \leq k \leq n.$

Of course, smallest element in $S$ is (by definition) $1$ and largest is $n - 1$ (since $\text{gcd}(n - 1, n) = 1$).

In few examples (specifically in cases $n = \{15, 20, 23\}$), I noticed that $S$ must be in form $S = \{k_1 = 1, k_2, ..., n - k_2 , k_r = n - 1)\}.$ In other words, $S$ always have even number of elements, $\varphi{(n)} = r \equiv 0 \pmod 2,$ (except trivial cases $n = \{1, 2\}$) and importantly sum of 1st and $r$th, 2nd and $(r - 1)$-th is always $n.$

How to prove it? Please use elementary methods, thanks.

Answer 1

Just follow your arguments. As S can be divided by two sets S1={ x : x in S, x< n/2}, and S2= { n-x: x in S, x

Answer 2

If $n$ has the canonical prime factorisation, $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$ then the general formula for $\varphi(n)$ is as follows, $$\varphi(n)=p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)\ldots p_k^{a_k-1}(p_k-1)$$

From here you can conclude.