For which positive integers $b>2$ do there exist infinitely many positive integers $n$ such that $n^{2}$ divides $b^{n}+1$?
This problem is a sort of union of IMO 1990/3 and IMO 2000/5. The answer is any \( b \) such that \( b+1 \) is not a power of 2. In the forwards direction, we first prove more carefully the following claim. 

**Claim**: If \( b+1 \) is a power of 2, then the only \( n \) which is valid is \( n=1 \).

\[ b^{2n} \equiv 1 \quad (\bmod p) \]

so the order of \( b \pmod{p} \) divides \( \gcd(2n, p-1) = 2 \). Hence \( p \mid b^2 - 1 = (b-1)(b+1) \). But since \( b+1 \) was a power of 2, this forces \( p \mid b-1 \). Then \( 0 \equiv b^n + 1 \equiv 2 \pmod{p} \), contradiction.

On the other hand, suppose that \( b+1 \) is not a power of 2 (and that \( b > 2 \)). We will inductively construct an infinite sequence of distinct primes \( p_0, p_1, \ldots \), such that the following two properties hold for each \( k \geq 0 \):

- \( p_0^2 \ldots p_{k-1}^2 p_k \mid b^{p_0 \ldots p_{k-1}} + 1 \),
- and hence \( p_0^2 \ldots p_{k-1}^2 p_k^2 \mid b^{p_0 \ldots p_{k-1} p_k} + 1 \) by the exponent lifting lemma.

This will solve the problem. Initially, let \( p_0 \) be any odd prime dividing \( b+1 \). For the inductive step, we contend there exists an odd prime \( q \notin \{ p_0, \ldots, p_k \} \) such that \( q \mid b^{p_0 \ldots p_k} + 1 \). Indeed, this follows immediately by Zsigmondy's theorem since \( p_0 \ldots p_k \) divides \( b^{p_0 \ldots p_{k-1}} + 1 \). Since \( \left( b^{p_0 \ldots p_k} \right)^q \equiv b^{p_0 \ldots p_k} \pmod{q} \), it follows we can then take \( p_{k+1} = q \). This finishes the induction.

To avoid the use of Zsigmondy, one can instead argue as follows: let \( p = p_k \) for brevity, and let \( c = b^{p_0 \ldots p_{k-1}} \). Then \( \frac{c^p + 1}{c + 1} = c^{p-1} - c^{p-2} + \cdots + 1 \) has GCD exactly \( p \) with \( c + 1 \). Moreover, this quotient is always odd. Thus as long as \( c^p + 1 > p \cdot (c + 1) \), there will be some new prime dividing \( c^p + 1 \) but not \( c + 1 \). This is true unless \( p = 3 \) and \( c = 2 \), but we assumed \( b > 2 \) so this case does not appear.

**Remark (On new primes)**: In going from \( n^2 \mid b^n + 1 \) to \( (nq)^2 \mid b^{nq} + 1 \), one does not necessarily need to pick a \( q \) such that \( q \nmid n \), as long as \( \nu_q(n^2) < \nu_q(b^n + 1) \). This is equivalent to \( \nu_q(b^n + 1) > \nu_q(n^2) \), which is true if \( \nu_q(b^n + 1) > 2 \nu_q(n) \). This is always true unless \( q = 3 \) and \( n = 2 \), but we assumed \( b > 2 \) so this case does not appear.

**Authorship comments**: I came up with this problem by simply mixing together the main ideas of IMO 1990/3 and IMO 2000/5, late one night after a class. On the other hand, I do not consider it very original; it is an extremely "routine" number theory problem for experienced contestants, using highly standard methods. Thus it may not be that interesting, but is a good discriminator of understanding of fundamentals.

IMO 1990/3 shows that if \( b = 2 \), then the only \( n \) which work are \( n = 1 \) and \( n = 3 \). Thus \( b = 2 \) is a special case and for this reason the problem explicitly requires \( b > 2 \).

An alternate formulation of the problem is worth mentioning. Originally, the problem statement asked whether there existed \( n \) with at least 3 (or 2018, etc.) prime divisors, thus preventing the approach in which one takes a prime \( q \) dividing \( \frac{b^n + 1}{n^2} \). Ankan Bhattacharya suggested changing it to "infinitely many \( n \)", which is more natural.

These formulations are actually not so different though. Explicitly, suppose \( k^2 \mid b^k + 1 \) and \( p \mid b^k + 1 \). Consider any \( k \mid n \) with \( n^2 \mid b^n + 1 \), and let \( p \) be an odd prime dividing \( b^k + 1 \). Then \( 2 \nu_p(n) \leq \nu_p(b^n + 1) = \nu_p(n / k) + \nu_p(b^k + 1) \) and thus

\[ \nu_p(n / k) \leq \nu_p\left(\frac{b^k + 1}{k^2}\right). \]

Effectively, this means we can only add each prime a certain number of times.