CGMO 2014 Problem 8

Let $n$ be a positive integer, and set $S$ be the set of all integers in $\{1,2,\dots,n\}$ which are relatively prime to $n$ . Set $S_1 = S \cap \left(0, \frac n3 \right]$ , $S_2 = S \cap \left( \frac n3, \frac {2n}3 \right]$ , $S_3 = S \cap \left( \frac{2n}{3}, n \right]$ . If the cardinality of $S$ is a multiple of $3$ , prove that $S_1$ , $S_2$ , $S_3$ have the same cardinality.