All-ukrainian math Olympiad task

Question

Prove that for any natural numbers a and b, max(a,b)>1, there are infinitely many natural n, such that the number $S(n)=a^n+b^{n+1}$ would be composite. Contest web page: https://matholymp.com.ua

Answer 1

If $a$ and $b$ have some common factor then this factor always divides $a^n + b^{n+1}$ which immediately yields the required result.

Otherwise, $\gcd (a,b) = 1$. Take any prime factor $p$ of $a+b^2$. Clearly $p$ cannot divide $a$ or $b$, because if it did it would have to divide the other (due to $p \mid a+b^2$), contradicting the fact that’s $a$ and $b$ are coprime.

By Fermat’s little theorem, $a^{p-1} \equiv b^{p-1} \equiv 1 \pmod p$. So if we let $n = k(p-1)+1$, we immediately obtain $a^n + b^{n+1} \equiv a+b^2 \equiv 0 \pmod p$, and so $p$ divides $a^n + b^{n+1}$. But since this is clearly greater than $a+b^2$ for all positive $k$, it is composite, and so since all $k$ work we obtain infinitely many composites, as required.