3. Let $p>3$ be a given prime number. For a set $S \subseteq \mathbb{Z}$ and $a \in \mathbb{Z}$, define

$$
S_{a}=\left\{x \in\{0,1, \ldots, p-1\} \mid(\exists s \in S) x \equiv_{p} a \cdot s\right\}
$$

(a) How many sets $S \subseteq\{1,2, \ldots, p-1\}$ are there for which the sequence $S_{1}, S_{2}, \ldots, S_{p-1}$ contains exactly two distinct terms?

(b) Determine all numbers $k \in \mathbb{N}$ for which there is a set $S \subseteq\{1,2, \ldots, p-1\}$ such that the sequence $S_{1}, S_{2}, \ldots, S_{p-1}$ contains exactly $k$ distinct terms.

(Milan Bašić, Miloš Milosavljević)

Time allowed: 270 minutes.

Each problem is worth 7 points.
3. Let $g$ be a primitive root modulo $p$. The sequence $S_{1}, S_{2}, \ldots, S_{p-1}$ is a permutation of $S_{1}, S_{g}, \ldots, S_{g^{p-2}}$. Since the sequence $S_{1}, S_{g}, S_{g^{2}}, \ldots$ is periodic with period $p-1$, its minimal period $d$ divides $p-1$ and the sets $S_{1}, S_{g}, \ldots, S_{g^{d-1}}$ are mutually distinct. The multiplications in the sequel are modulo $p$.

(b) It follows from above that $k \mid p-1$. On the other hand, for $k \mid p-1$ we can take $S=\left\{1, g^{k}, g^{2 k}, \ldots\right\}$.

(a) The minimal period of the sequence $S_{1}, S_{g}, S_{g^{2}}, \ldots$ is 2 , so $S_{0}=S_{2} \neq S_{1}$. Therefore $x \in S \Rightarrow g^{2} x \in S$. If $a, g a \in S$, then all $g^{n} a\left(n \in \mathbb{N}_{0}\right)$ are in $S$, i.e. $S=\{1,2, \ldots, p-1\}$ which is impossible. It follows that $x \in S \Rightarrow g x \notin S, g^{2} x \in S$. Thus $S$ is either $\left\{1, g^{2}, g^{4}, \ldots, g^{p-3}\right\}$ or $\left\{g, g^{3}, \ldots, g^{p-2}\right\}$, so the answer is two.