Question

数学竞赛题：求证:(2^m-1,2^n-1)=2^(m,n)-1

求证:(2^m-1,2^n-1)=2^(m,n)-1

Answer 1

不妨设m>=n，由带余除法得m=qn＋r，0<=r<=n。我们有，2^m－1＝2^(qn r)－2^r＋2^r－1＝2^r(2^qn－1)＋2^r－1。由此及2^n－1|2^qn－1得 (2^m－1，2^n－1 )＝ (2^n－1，2^r－1)。注意到(m,n)＝(n,r)，若r＝0，则(m,n)＝n，结论成立。若r＞0则继续对(2^n－1,2^r－1)作同样的讨论，由辗转相除法知，结论成立。其实这是初等数论里一个经典的结论，2可以换成任意大于1的整数，但证明的方法相对较难一点儿，当然也可以用上述方法。 如果你是初高中生想参加竞赛的话，希望多看一些相关书籍，拓宽一下自己的知识面。 推荐你一本数论书《初等数论》（第二版）潘承洞、潘承彪，北京大学出版社，比较细致，适合自学。

Answer 2

（m，n）=d m=dx n=dy (x,y)=1 由裴蜀定理则必存在p q>0使 px-qy=1 或qy-px=1(顺序不重要) 即证 （2^xd-1,2^yd-1）=2^d-1
先证（应该是知道的）：a-1整除a^p-1 因为a^p-1=(a-1)(a^(p-1)+……+1) 得证
故 2^d-1整除2^xd-1且整除2^yd-1 设（2^xd-1,2^yd-1）=k
故2^d-1整除k 现正k整除 2^d-1即可
又 2^(pxd)-1=(2^xd-1)(2^xd(p-1)+……+1)
2^(qyd)-1=(2^qy-1)(2^yd(q-1)+……+1)
得(2^xd-1)(2^(xd(p-1)+……+1)-(2^qy-1)(2^(yd(q-1)+……+1)
=2^(pxd)- 2^(qyd)=(2^（px-qy）d-1)2^(qyd)=(2^d-1)2^(qyd)
k显然与2^(qyd)互质 由k整除左边(2^xd-1)(2^xd(p-1)+……+1)-(2^qy-1)(2^yd（q-1)+……+1)得k整除右边=(2^d-1)2^(qyd)
由显然（k，2^(qyd) ）故k整除（2^d-1)
故k=2^d-1 故(2^m-1,2^n-1)=2^(m,n)-1