Bulgaria competition problems

It is easy to see that $(k, n) = (k + 1, n) = 1$. Then for any $k \in S$ there exists a unique $k_1 \in \{1, 2, \dots, n\}$ such that $(k_1, n) = 1$ and $k k_1 \equiv 1 \pmod{n}$. Since $k_1 + 1 \equiv k_1(k + 1) \pmod{n}$, then $(k_1 + 1, n) = 1$, i.e. $k_1 \in S$. Moreover, $(k-1)(k_1+1) \equiv k-k_1 \pmod{n}$ implies that $k \neq k_1$ if $k \neq 1$. Then the numbers from $S \setminus \{1\}$ can be divided into different pairs of the form $(k, k_1)$ and hence the wanted remainder is 1.