问题及解答

设 $m,n$ 是正整数, 证明 $(2^m-1,2^n-1)=2^{(m,n)}-1$. 

一般的, 对于正整数 $a,m,n$, 有

\[
(a^m-1, a^n-1)=a^{(m,n)}-1.
\]

[Hint] 使用辗转相除法证明.

求 $(m,n)$ 的过程和求 $(2^m-1, 2^n-1)$ 的过程是一致的.

Question:  考虑 $(a^m-1, b^n-1)$, 这里 $a,b$ 是大于1的正整数.

记 $d=(m,n)$, 且设 $m=kd$, $n=hd$. 于是根据问题2362 ,

\[
2^m-1=2^{kd}-1=(2^d)^k-1^k=(2^d-1)\Bigl((2^d)^{k-1}+(2^d)^{k-2}+\cdots+(2^d)^{1}+1\Bigr).
\]

于是 $(2^d-1)\mid(2^m-1)$. 同理,  $(2^d-1)\mid(2^n-1)$. 因此

\[
(2^d-1)\mid(2^m-1, 2^n-1).
\]