Divisors of $a^n+1$

Question

I am interested in the form of the odd prime divisors of $a^n+1$, for integers $a>1$ and $n>0$. Legendre, in 1793, has shown that every odd prime divisor $p \mid a^n+1$ either has the form $2nx+1$, with $x$ a positive integer, or is a divisor of $a^w+1$, where $w=n/s$, with $s$ odd. (See L. E. Dickson, History of the Theory of Numbers, Vol. I, p. 382.) This must be a well-known result. I am looking for a modern reference with a proof.

Answer 1

This is a simple result, so you might as well include the proof (where you need it). The cyclic subgroup of $(\mathbb{Z}/p\mathbb{Z})^\times$ generated by $a\bmod p$ contains $-1\bmod p$, hence its order $\mathrm{ord}_p(a)$ is even. Moreover, $w:=\mathrm{ord}_p(a)/2$ is the smallest positive integer with the property that $a^w\equiv -1\pmod{p}$, and $s:=n/w$ is a positive odd integer. If $s=1$, then $2n=\mathrm{ord}_p(a)$ divides $p-1$. If $s>1$, then $p$ divides $a^w+1$, where of course $w=n/s$ and $s>1$ is odd.

Answer 2

Legendre's Theorem for the factors of $a^n\pm b^n$ is Theorem 5.7 of Hans Riesel's book, Prime Numbers and Computer Methods for Factorization. The theorem and its proof are on pages 184-185.