# If $a^{m}+1\mid a^{n}+1$ then prove that $m\mid n$.

Let $$a$$ be an integer, $$a\ge2$$. If $$a^{m}+1\mid a^{n}+1$$ then prove that $$m\mid n$$.

Actually I know a similar proof which is, $$a^{m}-1\mid a^{n}-1 \iff m\mid n$$, but I can't prove this. I also need some examples of the question. Can't seem to find any correlation between the two proofs.
I seem to not find examples where $$a$$ is something different from $$2$$ and taking $$m=2$$.

• Specialize this more general result on their gcd (but a direct proof is easier) May 17, 2019 at 19:28
• Note: $3^3+1$ divides $3^9+1, 3^{15}+1, 3^{21}+1,...$ May 17, 2019 at 19:31
• @J.W.Tanner I see a pattern. Don't know if correct but I see it for $2^2+1,3^2+1,3^3+1,3^4+1$. That it is the third multiple,sixth multiple,ninth multiple of m which makes $a^n+1$ divisible by $a^m+1$. I guess it is correct for all primes . Thanks btw for it giving me little hint. Well seeing if I can find the proof or not. May 17, 2019 at 19:38

Suppose $$\gcd(m,n)=d$$. $$s=\gcd(a^{2m}-1,a^{2n}-1)=a^{2d}-1$$ But obviously $$a^m+1\mid s$$, so $$a^m+1\mid a^{2d}-1,$$ so $$m < 2d\Rightarrow d>\frac m2.$$ But $$d\mid m$$, so $$d=m$$ which means $$m\mid n$$.

• Nice solution, the kind of I was looking after. May 18, 2019 at 8:28
• @LoveInvariants For proofs of the first displayed equation see here. One is very similar to the proof in my answer (which proves a stronger result) May 18, 2019 at 12:41

$$U_{k} = a^{k} + 1$$ are terms of a Lucas sequence; hence, $$U_{m} | U_{n}$$ iff $$m | n$$.

• Can you attach an article about Lucas sequence? I can't find any about what you said. Jul 10, 2019 at 12:47
• Most of what I know about the Lucas sequences comes from D. H. Lehmer's "An Extended Throy of Lucas' Functions" published (1930) in the Annals of Mathematics. You should be able to access it with JSTOR or request it through interlibrary loan. I do not have an electronic copy. Jul 10, 2019 at 14:59
• Ok I will see . Jul 12, 2019 at 18:05

Hint  By below $$\, c = a^{M}+1\mid a^{(M,N)}+1\,$$ so $$\,\small \overbrace{(M,N)= M}^{\textstyle {\large \Rightarrow}\,M\mid N\ }\$$ (else $$\,\small (M,N)< M)$$

Theorem \,\ \begin{align}c\mid a^M+1\\ c\mid a^N+1\end{align}\, \Rightarrow\ \begin{align}&c\mid a^{\large d}+1\\ &\!d = {\small (M,N)}\end{align}\ \ \, Proof $$\$$ Let \,\begin{align} {\small M} &= dm\\ {\small N} &=\, dn\end{align}\,\ so $$\ (m,n)=1$$

$$\!\!\bmod c\!:\ a^{\large dm}\equiv -1\equiv a^{\large dn}\Rightarrow a^{\large 2dm}\equiv 1\equiv a^{\large 2dn}\,$$ thus $$\,{\rm ord}\, a^{\large 2d}$$ divides coprimes $$\,m,n\,$$ so it is $$1,\,$$ thus $$\,\color{#c00}{a^{\large 2d}\equiv 1}.\,$$ $$\,(m,n)=1^{\phantom{I^{I^I}}}\!\!\!\!\!\!\Rightarrow m\,$$ or $$\,n\,$$ odd, wlog $$\,n = 1\!+\!2j^{\phantom{I^I}\!\!\!\!}\,$$ so $$\ {-}1\equiv a^{\large dn}\!\equiv a^{\large d}(\color{#c00}{a^{\large 2d}})^{\large j}\!\equiv a^{\large d}$$

• The Theorem is excerpted from this Theorem which computes the gcd $\,(a^M+1,a^N+1)\ \$ More simply we could compute $\, a^N+1 \bmod a^M+1,\,$ but the Theorem is stronger and more insightful (and not much more work). May 17, 2019 at 23:20