THE 68th 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 $\phi (5^m)=4\cdot 5^{m-1}$, where $\phi$ is Euler's totient function; hence it is divisible by $8\cdot 5^m$. This ends the proof.