初等数论题，怎么证明:(2^m-1,2^n-1)=2^(m,n)-1

Question

好像用辗转相除法！

Answer 1

下面所有字母都表示正整数。

2^(ab)-1=(2^a)^b-1 = (2^a -1)((2^a)^(b-1)+...+2^a +1)
===》 2^a - 1 | 2^(ab)-1
于是： 2^(m,n)-1 | 2^m-1, 2^(m,n)-1| 2^n-1 ==》2^(m,n)-1 | (2^m-1, 2^n-1)
设 (m,n) = am - bn, (2^m-1, 2^n-1) = M.
则：
M|2^m-1 =》 M|2^(am) -1,
M|2^n-1 =》 M|2^(bn) -1,
==> M|((2^(am) -1) -(2^(bn) -1))
M| 2^(bn)*(2^(am-bn) -1)
===> M | 2^(am-bn) -1,
即： M| 2^(m,n) - 1
所以 (2^m-1,2^n-1)=2^(m,n)-1