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

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