bⁿ-1 is a Mersenne sequence, meaning that (b^m-1, bⁿ-1)=b^(m,n)-1. Let d=(m,n). This means that b^d-1 and b^m-1 have the same prime divisors. Let b^d=a, and m/d=M. Then a-1 and a^M-1 have the same prime divisors. Let p|a^M-1 be a prime. Then p|a-1, so p|a^M-a=a(a^M-1-1) so p|a^M-1. We continue like this until we get p|a²-1=(a-1)(a+1). We get that a-1 and (a-1)(a+1) have the same prime divisors. It's easy to get from here a+1=2^t, so b^d+1=2^t. If d is even then b^d is a perfect square which is 3(mod 4), which is false, so d is odd, so 2^t=b^d+1 is divisible with b+1, so b+1 is a power of 2.

I'll use a lemma: if $a>1,k>1$ and $a^k-1,a-1$ have the same prime factors, then $k$ is a power of $2$ and so is $a+1$. Assume the contrary, and let $p$ be an odd prime factor of $k$. Then any prime factor $q$ of $1+a+\ldots+a^{p-1}$ also divides $1+a+\ldots+a^{k-1}|a^k-1$, so it divides $a-1$, meaning that $1+a+\ldots+a^{p-1}\equiv p\pmod q\equiv 0\pmod q$, so $q=p$, so $1+a+\ldots+a^{p-1}=p^t,\ t>1$. Put $a=up+1$ and we'll get a contradiction fast (we find $1+a+\ldots+a^{p-1}\equiv p\pmod{p^2}$). This shows that $k$ is a power of $2$. If we take $r$ to be a prime which divides $a+1$, then it will divide $a^k-1$, and thus $a-1$, so $r=2$, which is what we wanted. Apply the lemma for $a=b^d$, where $d=(m,n)$, and $k=\frac md$. We find that all prime factors of $b^{kd}-1$ also divide $b^d-1$, where $k$ is a power of $2$. We also know that $b^d+1=2^t,\ t\ge 2$. Since a perfect square cannot be equal to $2^t-1,\ t\ge 2$, it means that $d$ is odd. Take a prime $r|b+1|b^2-1|b^{kd}-1$, so $r|b^d-1\equiv -2\pmod r$, so $r=2$, meaning that $b+1$ is a power of $2$, Q.E.D. P.S. The fact that $k$ is a power of $2$ is only useful for showing that $kd$ is even.

It is nice and easy: One can show that if the prime factors of $A^n-1$ and $A^m-1$ coincide, then $n=2, m=1$ and $A+1=2^t$. And also using this one can show that If the prime factors of $A^m-1$ are a subset of the ones from $A^n-1$ then $m|n$ or $m=2$ and $A+1=2^t$ and a list of nice corollaries follows: The nicest Corollary: $A_1^{x_1}-A_2^{x_2} A_2^{x_3}....A_n^{x_n}=1$ with $A_i$ given integers has at most one solution $(x_1,x_2...,x_n)$ with $x_1>1$ and $x_i>0$. For example $3^x-2^y7^z=1$ has at most one solution $(x,y,z)$

Lets say m>n Because \[ (b^m - 1 , b^n - 1 ) = b^{(m,n)} - 1 \] then $ b^{(m,n)} - 1$ and $ b^m - 1$ must have same prime divisors. so now put $ (m,n) = \zeta , m = k \zeta , a = b^\zeta$ so now it is clear that $ a - 1 , a^k - 1$ share same prime divisors. now suppose $ P$ is one of $ k$ prime divisors. because $ a^p - 1 \mid a^k - 1 , a - 1 \mid a^p - 1$ , $ a - 1, a^p - 1$ also must have same prime divisors. Now lets put : $ \alpha = a^{p - 1} + a^{p - 2} + ... + 1$ If $ q$ be a prime divisor of $ \alpha$ , Then $ a - 1 \equiv 0 (mod q)$ , as a result, $ \alpha \equiv 1 + 1 + 1 + ... + 1 \equiv p$ so that means $ q = p$ and the obviously we can say that $ \alpha = p ^ \phi$ in order to find out what $ \phi$ can be , we write : $ a = pt + 1$ ( $ a - 1 \equiv 0, (mod p )$ ) now if we look closer we easily see that : $ a^r \equiv (pt + 1)^r \equiv \sum(j = 0 ,\rightarrow r) (pt)^j * C(r,j) \equiv C(r,1)pt + 1 (mod p^2 )$ $ \Rightarrow \alpha \equiv \sum (r = 0 \rightarrow p - 1) rpt + 1 \equiv pt \frac {(p - 1)p} {2} + p \equiv p (mod p^2)$ now if $ p$ is prime and odd, $ \phi = 1 \rightarrow = a^p - 1 + ... + 1 = p$ and this contradicts $ a > 1$ , therefore p should be even, and that is $ p = 2$ so prime divisors of $ a^2 - 1 , a - 1$ are the same. but $ (a + 1) - (a - 1) = 2$ and so $ a + 1 = 2^ w$ ,,, inother words , $ b^\zeta + 1$ is a power of $ 2$ , and again ofcourse $ \zeta$ cant be even , because if be, then $ b^\zeta + 1 \equiv 2 (mod 4)$ and because $ b^\zeta + 1 = 2 ^ w$ we would conclude that $ b = 1$ (since b is odd) therefore $ \zeta$ is odd and $ b + 1 \mid b^\zeta + 1$ and we are all set, $ b + 1$ is a power of $ 2$ .

A good solution ,Robert_89 , but there are too many mistakes in your solution I had tried my best to understand your solution In order to take profits from Mathlinks . You should pratise English more .

Without loss of generality, suppose $m < n$. If $b+1$ is not a power of 2 and $n \neq 6$, then by Zsigmondy's theorem we can find some prime $p$ such that $p | b^n - 1$ but $p \not | b^m - 1$, which is impossible. Furthermore, $2^1 - 1 = 1$, $2^2 - 1 = 3$, $2^3 - 1 = 7$, $2^4 - 1 = 3 \cdot 5$, $2^5 - 1 = 31$, and $2^6 - 1 = 3^2 \cdot 7$, so $2^6 - 1$ does not have the same set of prime factors as any of $2^i - 1$ with $1 \leq i \leq 5$. Hence, $n \neq 6$, so we may conclude that $b+1$ is a power of 2. Note that Zsigmondy's theorem tells us that $b+1$ must be a power of two and that $(m,n) = (1,2)$ or $(m,n) = (2,1)$.

sam-n wrote: Let $ b, m, n$ be positive integers such that $ b > 1$ and $ m \neq n.$ Prove that if $ b^m - 1$ and $ b^n - 1$ have the same prime divisors, then $ b + 1$ is a power of 2.

Let $d = (m,n)$, with $m = dm_0, n = dn_0$ and $(m_0,n_0) = 1$. We have that $(b^n - 1, b^m - 1) = b^d - 1$, so we get that $b^{dm_0} - 1 = (b^d - 1)\cdotM$ $b^{dn_0} - 1 = (b^d - 1)\cdotN$ Notice that if there is a new prime $p$ that divides $M$ but does not divide $b^d -1$, then it divides $b^{dm_0} - 1$, which due to the problem implies that this prime divides $b^{dn_0} - 1$. But this is would implie that $p$ divides $(b^{dm_0} - 1, b^_{dn_0} - 1) = b^d - 1$, which is a contradiction. Hence, every prime that divides $b^d - 1$ must divide $b^{dm_0} - 1$ and vice-versa.

Bruhhh direct zsigmondy; Let $m>n$ from zsigmondy's theorem there is must be non-common prime divisor. But zsigmondy does not work at these two case Case 1: $b=2$ and $n=6$ trying for $m=1,2,3,4,5$ we get that no sol. Case 2: $b+1=2^i$ from this statement we're done.

sam-n wrote: Let $ b, m, n$ be positive integers such that $ b > 1$ and $ m \neq n.$ Prove that if $ b^m - 1$ and $ b^n - 1$ have the same prime divisors, then $ b + 1$ is a power of 2. WLOG $m>n$: $gcd(b,1)=1$ By Zsigmondy's Theorem: $\exists$ prime $p/ p|b^m-1, p\nmid b^n-1$ $(\Rightarrow \Leftarrow)$ But there is an exception: $b+1=2^t_\blacksquare$

easy one Without losing generality, suppose that $m<n.$ Since $b^m-1$ and $b^n-1$ share the same prime divisors, there does not exist some prime $p$ such that $p\mid b^n-1$ and $p\nmid b^i-1$ for all $i\in\{1,2,\cdots,n-1\}$, as $m<n$ implies that $m\in\{1,2,\cdots,n-1\}.$ Thus, the triplet $(b,1,n)$ must be an exception to Zsigmondy's Theorem, implying that either $b+1$ is a power of $2$ and $n=2$ or $(b,n)=(2,6).$ If we have the latter case, then $b^n-1=2^6-1=63=3^2\cdot7.$ One can check that there does not exist an element of $\{2^1-1,2^2-1,\cdots,2^5-1\}$ such that its prime divisors are exactly $3$ and $7$. Thus this case fails, so it follows that $b+1=2^k$ for some positive integer $k$ and $n=2$, as desired. $\blacksquare$

Zsygmondy's theorem kills it

Just use zsigmondy

Direct application of Zsigmondy theorem.