Belarus — Selection and Training Session

a) (Solution of A.Ivanin, O.Volod'ko, A.Zhuk.) (Further we put $p_{n+1} = p_1$.)
Let $p_k$ be the greatest number among all $p_i$ ($i = 1, 2, \ldots, n$). The condition $a^{p_i} \equiv 1 \pmod{p_{i+1}}$ implies that $a$ and $p_i$ are relatively prime for all $i$. Then $a^{p_{k+1}-1} \equiv 1 \pmod{p_{k+1}}$ by Little Fermat Theorem. Since, by the problem condition, $a^{p_k} \equiv 1 \pmod{p_{k+1}}$, we also have $a^d \equiv 1 \pmod{p_{k+1}}$ where $d = \text{GCD}(p_{k+1}-1, p_k)$.
But from $d \mid p_k$ it follows that $d = p_k$ or $d = 1$. If $d = p_k$ then $p_{k+1} - 1 \ge p_k$, $p_{k+1} > p_k$, a contradiction. Hence $d=1$ and $a \equiv 1 \pmod{p_{k+1}}$, q.e.d.

b) Take any prime $p_1$. By the Dirichlet theorem, we can choose a sequence of primes $p_1, \ldots, p_n$ such that $p_2 - 1 \mid p_1,\ p_3 - 1 \mid p_2,\ \ldots,\ p_n - 1 \mid p_{n-1}$.

Let $p_{k+1} - 1 = p_k b_{k+1}$, $k = 1, \ldots, n - 1$. Further, choose for any $l = 2, \ldots, n$ a primitive root $x_l \pmod{p_l}$ and set $a_k = x_k^{b_k}$. In particular, $a_{k+1} \not\equiv 1 \pmod{p_{k+1}}$ and $a_{k+1}^{p_k} = x_{k+1}^{p_{k+1}-1} \equiv 1 \pmod{p_{k+1}}$. Now by the Chinese Remainder Theorem, there exists an $a$ such that $a \equiv 1 \pmod{p_1}$ and $a \equiv a_{k+1} \pmod{p_k}$ for $k = 1, \ldots, n-1$. This $a$ satisfies the condition.