Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

The required primes are $2$ and $5$. Begin by noticing that if $a_1$ is any even integer, then $a_{n-1}$ is an integral power of $n$ for all $n \ge 3$. Thus, if $n \ge 3$, then $(a_n - 1)/a_{n-1} = ((n+1)^{n_k} - 1)/n^{k+1}$ for some non-negative integer $k$. An easy induction on $k$ shows that $(n+1)^{n_k} - 1$ is divisible by $n^{k+1}$ for all non-negative integers $k$, so $(a_n - 1)/a_{n-1}$ is an integer for $n \ge 3$. Consequently, if $n \ge 3$, then

$$a_n \left(1 - \frac{1}{a_1}\right) \left(1 - \frac{1}{a_2}\right) \dots \left(1 - \frac{1}{a_n}\right) = (a_1 - 1) \cdot \frac{a_2 - 1}{a_1} \cdot \frac{a_3 - 1}{a_2} \dots \frac{a_n - 1}{a_{n-1}}$$

is an integer, provided that $a_2 - 1$ is divisible by $a_1$. On the other hand, since $a_1$ is coprime to $a_1 - 1$, the product $a_2\left(1 - \frac{1}{a_1}\right)\left(1 - \frac{1}{a_2}\right) = (a_1 - 1)(a_2 - 1)/a_1$ is an integer if and only if $a_2 - 1$ is divisible by $a_1$.

Let $a_1 = 2a$, where $a$ is a positive integer. Then $a_2 = 3^a$, and the general problem consists in determining $a$ so that $3^a - 1$ is divisible by $2a$. This is clearly the case if $a$ is a power of $2$, so $p = 2$ is a solution.

The other case in the problem is $a = 4p^m$, where $p$ is an odd prime. The divisibility condition implies that $p$ is a divisor of $3^{4p^m} - 1$, so $p \ge 5$. Since $p$ is coprime to both $3$ and $p-1$, the latter must be a divisor of $4$, so $p=5$. The number $3^{4 \cdot 5^m} - 1$ is clearly divisible by $8$, and it is divisible by $5^m$, since $\varphi(5^m) = 4 \cdot 5^{m-1}$, where $\varphi$ is Euler's totient function; hence it is divisible by $8 \cdot 5^m$. This ends the proof.