Assume $m>n$. By Zsigmondy's theorem, if $m \neq 2,6$, $b^m-1$ has a prime factor not dividing any $b^k-1$ for $k<m$. This especially holds for $k=n$, thus we get $m=2,6$ (and $b=2$ in the latter case). If $m=2$, we have $b^2-1=(b+1)(b-1)$. Every prime $p|b+1$ also divides $b-1$, giving $p|2$. Thus $b+1$ can have only have the prime divisor $2$, giving the result. If $m=6$, then we just have to check $5$ cases for $n$, left out now. I know that a lot of people consider Zsigmondy's theorem to brutal, but since we can proof it on an elementary way and it kills really a lot of olympiad problems, I see no reason not to use it. [To see what Zsiygmondy's theorem says, look at http://mathworld.wolfram.com/ZsigmondyTheorem.html ]

hello.unfortunately i didnt read Zsigmondys Theorem yet but lets check my solution: let m+n=k , now :using induction on k ($k\geq3): $ **consider $\forall m,n$ such that :$ k>m+n\geq1$ b+1 is power of 2. now we prove it for m+n=k consider n>m: if k=3 then n=2,m=1 wich this case is little obvious. Lemma 1)n is not divisible by m: because $b^t-1$ has a prime factor not dividing any b-1 : it can easily proved by exponent lemma and this:$a^n-b^n>n(a-b)$ so $gcd(m,n) \neq m$ if gcd(m,n)=t $ \Longrightarrow gcd(b^n-1,b^m-1)=gcd(b^m-1,b^t-1) \Longrightarrow b^m-1 , b^t-1$ have the same set of prime divisors and m+t <m+n=k . so according to ** b+1 must be power of2

i think we can find the best solution for this problem in this link http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=338898&p=1815036#p1815036

It is trivial by using zigmondy theorem.

Yes but Zsigmondy's Theorem isn't much trivial!!

andria wrote: It is trivial by using zigmondy theorem. A proof of Zsigmondy's theorem requires a lot of study and work !!

I think no $m,n,b$ statisfies problem's condition. Here is my proof. Suppose $m$ is odd. Let $d=\gcd(m,n)$ and $m=ad$. So $a,d$ are odd Because $b^m-1,b^n-1$ have same set of prime divisors so $b^{ad}-1,b^{d}-1$ have same set of prime divisors. Let $p$ be any prime such that $p\mid \dfrac{b^{ad}-1}{b^d-1}$. So $p\mid b^{ad}-1$ hence $p\mid b^d-1$. It's also not hard to prove that $p$ is odd. Let $j=ord_p(b)$. So $j\mid d$. By lifting the exponent lemma; $v_p\left(\dfrac{b^{ad}-1}{b^d-1}\right)=v_p(b^{ad}-1)-v_p(b^d-1)=v_p(b^j-1)+v_p\left(\dfrac{ad}{j}\right)-v_p(b^j-1)-v_p\left(\dfrac{d}{j}\right)=v_p(a)$. So $a=\dfrac{b^{ad}-1}{b^d-1}=b^{(a-1)d}+b^{(a-2)d}+b^{(a-3)d}+...+1>1+1+1+...+1=a$ Contradiction. So both $m,n$ must be even. Assume $m=2^rc, n=2^sd$ when $c,d$ are odd and WLOG $r<s$ So $(b^{2^r})^{c}-1, (b^{2^r})^{2^{s-r}d}-1$ have same set of prime divisors which implies that $c$ is even. So no such $b,m,n$ statisfies problem's condition.

I apologize to everyone for my solution being similar to that of ZetaX. But I'm beginner in Zsigmondy's theorem.I want to solve problem by using Zsigmondy's theorem. WLOG $m>n$.Except for case1:$(b,m)=(2,6)$ or case2:$m=2$ and $b+1$ is power of $2$,Zsigmondy's theorem can be applied.If neither case1 nor case2,by Zsigmondy's theorem,∃$p$(prime) s.t. $b^m-1$ is divisible by $p$ but $b^n-1$ isn't divisible by $p$ which is absurd.If case1,the set of prime divisors of $b^m-1$ is $\{ 3,7\}$.That of $b^5-1$ is $\{ 31\}$,that of $b^4-1$ is $\{ 3,5\}$,that of $b^3-1$ is $\{ 7\}$,that of $b^2-1$ is $\{ 3\}$,that of $b-1$ is $\phi$.This is contradiction.Therefore case2 must hold,and then $b+1$ is power of $2$.The proof is completed.$\blacksquare$