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$.
Please help. I think 4-5 examples might help me to see the proof.
 A: 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$. 
A: 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}$
A: $U_{k} = a^{k} + 1$ are terms of a Lucas sequence; hence, $U_{m} | U_{n}$ iff $m | n$.
