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

Question

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$.
Please help. I think 4-5 examples might help me to see the proof.

Answer 1

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

Answer 2

Theorem $\,\Rightarrow\, c = \overbrace{a^{M}+1\mid a^{(M,N)}+1}^{\small\textstyle \Rightarrow \color{#90f}{M \le (M,N)}}\,\Rightarrow \color{#90f}{(M,N)= M}\Rightarrow M\mid N $

Theorem $\,\ \begin{align}c\mid a^M+1\\ c\mid a^N+1\end{align}\,$ $\Rightarrow\ \begin{align}&c\mid \color{#0a0}{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 2d\color{darkorange}m}\equiv 1\equiv a^{\large 2d\color{darkorange}n}\,$ thus $\,{\rm ord}\: a^{\large 2d}$ divides coprimes $\,\color{darkorange}{m,n}\,$ so it is $1,\,$ so $\,\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 $\ \color{#0a0}{{-}1}\equiv a^{\large dn}\!\equiv a^{\large d}(\color{#c00}{a^{\large 2d}})^{\large j}\!\equiv \color{#0a0}{a^{\large d}}$

Answer 3

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