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,\dots ,n$). The condition $a^{p_i}\equiv 1(\mathrm{mod}{p}_{i+1})$ implies that $a$ and $p_i$ are relatively prime for all $i$. Then $a^{p_{k+1}-1}\equiv 1(\mathrm{mod}{p}_{k+1})$ by Little Fermat Theorem. Since, by the problem condition, $a^{p_k}\equiv 1(\mathrm{mod}{p}_{k+1})$, we also have $a^d\equiv 1(\mathrm{mod}{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(\mathrm{mod}{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,\dots ,p_n$ such that $p_2-1\mid p_1,p_3-1\mid p_2,\dots ,p_n-1\mid p_{n-1}$.

Let $p_{k+1}-1=p_k{b}_{k+1}$, $k=1,\dots ,n-1$. Further, choose for any $l=2,\dots ,n$ a primitive root $x_l(\mathrm{mod}{p}_l)$ and set $a_k=x_k^{b_k}$. In particular, $a_{k+1}\not\equiv 1(\mathrm{mod}{p}_{k+1})$ and $a_{k+1}^{p_k}=x_{k+1}^{p_{k+1}-1}\equiv 1(\mathrm{mod}{p}_{k+1})$. Now by the Chinese Remainder Theorem, there exists an $a$ such that $a\equiv 1(\mathrm{mod}{p}_1)$ and $a\equiv a_{k+1}(\mathrm{mod}{p}_k)$ for $k=1,\dots ,n-1$. This $a$ satisfies the condition.