Bulgarian Mathematical Competitions

Solution:
First we shall prove the following:

LEMMA. Let $p \geq 3$ be an odd divisor of $b$. Then there exists an odd prime $q$ that divides $(b+1)^{p}-1$ but does not divide $b$.

Proof of the lemma. If $b=pc$, then
$$\begin{aligned} (b+1)^{p}-1 & =b\left((b+1)^{p-1}+\cdots+b+1\right) \\ & =b\left(B b^{2}+\frac{p(p-1)}{2} b+p\right)=b p\left(b\left(B c+\frac{p-1}{2}\right)+1\right)=b p d \end{aligned}$$
and it remains to choose a prime divisor of $d$. Note that $d$ is odd (if $b$ is even, then $d=b K+1$ is odd; if $b$ is odd, then $(b+1)^{p}-1$ is odd, and hence $d$ is odd, too).

We shall prove now that if $a \neq 2^{k}+1$, then there exists a sequence of odd primes $p_{1}, p_{2}, \ldots$ such that $p_{1}$ divides $a-1$, and if $P_{n}=a^{p_{0} p_{1}} p_{n}-1$ (here $p_{0}=1$ ), then $p_{n+1}$ divides $P_{n}$, but does not divide $P_{n-1}$, $n \geq 1$.

Let $p_{1}$ be an odd prime divisor of $a-1$ and we have already chosen the primes $p_{1}, \ldots, p_{k}$. Applying the lemma for $b=P_{k}$ and $p=p_{k}$, we find an odd prime $p_{k+1}$ that divides $P_{k}$ but does not divide $P_{k-1}$.

Since $P_{k-1}$ is divisible by $p_{1}, p_{2}, \ldots, p_{k}$, we conclude that $p_{k+1}$ differs from them. Therefore the numbers $p_{1}, p_{2}, \ldots, p_{k}$ have the required property.

If $a=2^{l}+1, l \geq 2$, then $a^{2} \neq 2^{m}+1$ and it remains to multiply by 2 the numbers already found for $a^{2}$.

Remark. It can be proved that if $n$ divides $2^{n}-1$, then $n=1$, and if $n$ divides $3^{n}-1$ then $n=1, n=2$, or $n$ is divisible by 4. The above solution shows that for $a=3^{4}$ there exist infinitely many positive square-free odd integers $n$ such that $4 n$ divides $3^{4 n}-1$.