Determine all $m,n \in \mathbb{N}$ such that $(5^m-1,5^n+1)=2$ 
Determine all $m,n \in \mathbb{N}$ such that $$\gcd(5^m-1,5^n+1)=2$$

First attempt:
Say $d= (5^m-1,5^n+1)$, then $d|5^m-1$ and $d|5^n+1$ so $d|5^m+5^n$.
If $m=n$ then $d|2$ so $d=2$ since $5^m-1$ and $5^n+1$ are both odd.
If $m>n$ then $d|5^n(5^{m-n}+1)$. Since $5\not|d$ we have by Euclid lemma $d|5^{m-n}+1$ and now what?

Second :
We notice if $m=2n$ then $$5^m-1 = (5^n-1)(5^n+1)$$ so $(5^m-1,5^n+1)=5^n+1$.
The same is true if $m= kn$, $k$ even. So perhaps it is reasonable to believe that if $m\ne kn$, $k$ even then $d=2$. But I'm not sure.
 A: Numeric experiments suggest the following: $m$ is any number, and $n$ is any number divisible by the same or greater maximum power of $2$ as $m$. That is, if $m$ is odd, then $n$ is any number; if $m$ is divisible by 2, but not by 4, then $n$ is any even number, and so on.

Why would that be true?
Well, the necessity of the condition is obvious: if $n=2^k\cdot l,\;2\nmid l$, but $2\mid{m\over2^k}$, then $2^{2^k}+1|2^n+1$, but at the same time $2^{2^k}+1|2^{2^{k+1}}-1\mid2^m-1$.
Now to the point of sufficiency. Suppose my condition is met. Apparently, if $m\leqslant n$, then
$$\gcd(5^m-1,5^n+1)=\gcd(5^m-1,5^n+1-5^{n-m}(5^m-1))=\\=\gcd(5^m-1,5^{n-m}+1)\tag1$$
On the other hand, if $m\geqslant2n$, then
$$\gcd(5^m-1,5^n+1)=\gcd(5^m-1-5^{m-2n}(5^n+1)(5^n-1),5^n+1)=\\=\gcd(5^{m-2n}-1,5^n+1)\tag2$$
This is pretty much like Euclid algorithm, only it limps on one leg, hence we may call it lame Euclid algorithm. Because of that, it would not get us all the way down: we'll get stuck at some point where $n<m<2n$. Then our lame Euclid will need crutches to jump over this hole:
$$\gcd(5^m-1,5^n+1)=\gcd(5^m-1-5^{m-n}(5^n+1),5^n+1)=\\
=\gcd(5^{m-n}+1,5^n+1)=\gcd(5^{m-n}+1,5^n+1-5^{2n-m}(5^{m-n}+1)=\\
=\gcd(5^{m-n}+1,5^{2n-m}-1)\tag3$$
See that? $2n-m$ (which is divisible by the same maximum power of 2 as $m$) takes the former role of $m$, while $m-n$ (which is divisible by the same or maybe greater power of 2) takes the role of $n$. So we got further down and the condition is still met, hence we may continue.
How will all this end? Well, it could have ended on step 2 with $m-2n=0$ and a non-trivial gcd of $5^n+1$, but this is impossible because of the condition. What remains is $n-m=0$ on step 1, which produces the desired $\gcd=2$.
Q.e.d.
