Suppose that $q$ divides $a^p+1$. Then $a^p \equiv -1 \pmod q$. Note that $(a^p)^2=a^{2p}$. So $a^{2p}\equiv 1 \pmod q$.
Let $e$ be the smallest positive integer such that $a^e\equiv 1 \pmod q$. Then $e$ divides $2p$. In principle, there are $4$ possibilities to examine: (i) $e=1$; (ii) $e=2$; (iii) $e=p$; (iv) $e=2p$.
Possibility (i): If $e=1$, then $a \equiv 1\pmod{q}$. This cannot happen, because we were told that $a^p \equiv -1\pmod{q}$. But $1\not\equiv -1\pmod{q}$, since $q$ is odd.
Possibility (ii): If $e=2$, then $a\equiv -1\pmod{q}$, so $q$ divides $a+1$.
Possibility (iii) If $e=p$, we reach a contradiction, since $a^p\equiv -1 \pmod{q}$, and $1\not\equiv -1\pmod{q}$.
Possibility (iv): Recall that by the minimality of $e$, the number $e$ must divide any $k$ such that $a^k\equiv 1\pmod{q}$. Since $a$ cannot be divisible by $p$, we have, by Fermat's Theorem, $a^{q-1}\equiv 1\pmod{q}$. Thus if $e=2p$, the number $2p$ must divide $q-1$. Let $q-1=(2p)k$. Then $q=2kp+1$.
So the only live possibilities are (ii) and (iv). One yields that $q$ divides $a+1$, and the other yields that $q$ is of the shape $2kp+1$. Both can happen.