A new prime divides $a^p+1$

Question

Let $a\in \mathbb{Z}$ and $p, q\in\mathbb{P}$. If $q\mid a+1$, there exists at least a prime $r \neq q$ such that $r\mid a^p+1$ (except for some trivial cases).

Answer 1

Hint: Deal with $p=2$ separately. For odd $p$, We have $a^p+1=(a+1)(a^{p-1}-a^{p-2}+\cdots +1)$. Evaluate $a^{p-1}-a^{p-1}+\cdots+1$ modulo $q$.

Added: As a follow up, we show how to complete the argument. Use the hint above. Since $a\equiv -1\pmod{q}$, we find that $a^{p-1}-a^{p-2}+\cdots +1\equiv p\pmod{q}$. If $p\ne q$, that means $a^p+1$ is not a power of $q$, so there is a prime other than $q$ that divides $a^p+1$. Also, unless $a+1$ is a power of $q$, there is a prime other than $q$ that divides $a^p+1$. The sole case that remains is the possibility $p=q$, with $a+1=q^t$ for some $t$.

Then $a^p=(q^t-1)^q$. Expand, using the Binomial Theorem, and add $1$. We get $$a^p+1=q^{qt}-\binom{q}{1}q^{t(q-1)} +\cdots -\binom{q}{q-2}q^{2t}+\binom{q}{q-1}q^t.\tag{$1$}$$ The binomial coefficients, except for the leading $1$, are divisible by $q$. It follows that the highest power of $q$ that divides $(1)$ is $q^{t+1}$. Thus $(1)$ can only be a power of $q$ if it is equal to $q^{t+1}$. We show this cannot happen if $q^t\ge 5$. (It can and does happen if $q=3$ and $t=1$.)

The rest follows from simple inequalities. If $qt\ge 5$, then $q^t-1\ge \frac{4}{5}q^t$. We want to show that
$$\frac{4^q}{5^q}(q^t)^q \overset{?}{\ge} q^{t+1}\tag{$2$}$$ or equivalently that
$\frac{4^q}{5^q}(q^t)^{q-1}\ge q$. There are now two cases, (i) $q\ge 5$ and (ii) $q=3$ and $t\gt 1$.

In Case (i) it is enough to show that $\frac{4^q}{5^q}q^{q-1}\ge q$. Since $q\ge 5$, the left side is $\ge 4^q q^{-1}$. So we want to show that $4^q\ge q^2$, which is obvious.

The inequality for Case (ii) is handled similarly.

Answer 2

Assume otherwise. Then $a^p+1=q^k$ for some $k$. The only case of adjacent powers like this is $$2^3+1=3^2.$$