Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?

share|cite|improve this question
up vote 6 down vote accepted

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}$$

share|cite|improve this answer
Bill, thanks for the update. – lab bhattacharjee Aug 22 '12 at 18:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.