Bulgaria

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(\mathrm{mod}n)$. Since $k_1+1\equiv k_1(k+1)(\mathrm{mod}n)$, then $(k_1+1,n)=1$, i.e. $k_1\in S$. Moreover, $(k-1)(k_1+1)\equiv k-k_1(\mathrm{mod}n)$ implies that $k\ne k_1$ if $k\ne 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.