elementary number theory - When does $n$ divide $a^d+1$?

$\newcommand{\ord}{\operatorname{ord}}$

For what values of $n$ will $n$ divide $a^d+1$ where $n$ and $d$ are positive integers?

Apparently $n$ can not divide $a^d+1$ if $\ord_n a$ is odd.

If $n\mid (a^d+1)\implies a^d\equiv -1\pmod n\implies a^{2d}≡1\pmod n \implies\ord_na\mid 2d$ but $\nmid d$.

For example, let $a=10$, the factor(f)s of $(10^3-1)=999$ such that $\ord_f10=3$ are $27,37,111,333$ and $999$ itself. None of these should divide $10^d+1$ for some integer $d$.

Please rectify me if there is any mistake.

Is anybody aware of a better formula?

Answer

There are various useful bits of information that one may deduce about factors of integers of the form $\rm\:b^n\pm 1.\:$ A good place to learn about such is Wagstaff's splendid introduction to the Cunningham Project, whose goal is to factor numbers of the form $\rm\:b^n\pm 1.\:$ There you will find mentioned not only old results such as Legendre (primitive divisors of $\rm\:b^n\pm 1\:$ are $\rm\,\equiv 1\pmod{2n},$ but also newer results, e.g. those exploiting cyclotomic factorizations. e.g. see below.

---

Often number identities are more perceptively viewed as special cases of function or polynomial identities. For example, Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations (e.g. see below).

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$