<s>[INST] Let $m,n,b \in \mathbb{N} $ with $b > 1$ and $m \neq n$. Let $m,n,b \in \mathbb{N} $ with $b > 1$ and $m \neq n$.
If $b^{m}-1 $ and $b^{n}-1 $ have the same prime divisors, prove that $b+1$ is a power of 2.
I know that $b^{m}-1 = (b-1)(b^{m-1}+b^{m-2}+\cdots+ 1 )$ and same for $b^{n}-1$
Or maybe, I should consider $b^{m}-1 -b^{n}+1 = b^{m} - b^{n}$.
I really have no idea on how to tackle this problem.
 [/INST] Please note that this solution is due to Kamil Duszenko.
Consider first the case $n = 1$. So suppose first that $a - 1$ and $a^m - 1$ have the same prime divisors. If a prime p divides m, then $a - 1$ divides $a^p - 1$, and $a^p - 1$ divides $a^m - 1$, so a - 1 and $a^p - 1$ have the same prime divisors. But $a^p - 1 = (a - 1) L$, where $L = a^{p-1} + a^{p-2 }+ ... + a + 1$. So if a prime q divides L, then it must divide $a^p - 1$ and hence $a - 1$. But $L = (a - 1) (a^{p-2} + 2 a^{p-3} + ... + p-1) + p$, so any prime q dividing L and $a - 1$ must also divide p. So L must be a power of p, m must be a power of p, and p must divide $a - 1$. In other words, $a = 1 \, mod \, p$. Hence $(a^{p-2}+ 2 a^{p-3 }+ ... + p-1) = 1 + 2 + ... + p-1 = p(p-1)/2 \, mod \, p$. But if $p > 2 \, , p(p-1)/2 = 0 \, mod \, p$, so $L = p^2 + p \, mod \, p^2$. But L is a power of p, so $L = p$. Contradiction, since L is obviously > p (or p > 2). Hence p must be 2. Hence $L = a + 1$, and $ a + 1$ is a power of 2.
Now take the general case. Suppose d is the greatest common divisor of m and n. Put $m = dM \, ,  n = dN$ and $ a = b^d$, so that $a^M - 1$ and $a^N - 1$ have the same prime divisors, and M, N are relatively prime. Take positive integers h, k such that $hM - kN = 1$, then $(a^{hM}- 1) - (a^{kN} - 1) = a^{hM} - a^{kN} = a^{kN}(a - 1)$. So if s > 1 divides $a^M - 1$ and $a^N - $1, then it also divides $a^{hM} - 1$ and $a^{kN} - 1$ and hence also $a^{kN}(a - 1)$. It cannot divide $a^{kN}$, so it must divide $a - 1$. So the greatest common divisor of $a^M - 1$ and $a^N - 1$ must divide $a - 1$. But $a - 1$ divides both, so the greatest common divisor is $a - 1$. So $a- 1$ must also have the same prime divisors as $a^M - 1$. It follows from the special case that $a + 1 = b^d + 1$ is a power of 2. Since $b > 1, b^d + 1 > 2$, so $ b^d + 1$ is certainly divisible by 4. If d is even, then $odd^d = 1 \, mod \, 4$ and $even^d = 0 \, mod \, 4$, so $b^d + 1 = 2 $ or $1 \, mod \, 4$. Hence d must be odd. Hence $b + 1$ divides $b^d + 1$, so $b + 1$ is also a power of 2.
</s>