问题及解答

求 $\text{gcd}(2^n+1,2^m+1)$, where $n > m$.

类似的, 讨论

$\text{gcd}(2^n\pm 1,2^m\pm 1)$, where $n > m$.

Example:

$\text{gcd}(2^6+1,2^2+1)=5$.

注意有这样一个引理

Lemma: 设 $a,b\in\mathbb{Z}^+$, $x\in\mathbb{Z}$, 则有

\[
\text{gcd}(x^a-1,x^b-1)=\Bigl|x^{\text{gcd}(a,b)}-1\Bigr|.
\]