注明： 符号 | 是“整除”的意思

命题：m 是正偶数， n 是正整数， 则 GCD(2^m-1, 2^n+1)=1

首先， 如果， n=m， s|2^m-1, s|2^m+1, 则 s|（2^m+1)-(2^m-1), 即 s|2
但是 2 不能整除 2^m-1, 所以 s=1. 所以命题对 n=m 成立。

设 s|2^m-1, s|2^n+1。则 GCD（2，s）=1， 因为 2 不能整除 2^m-1

不失一般性， 可以假设 n<m。 如果 n>m, 则 s | （2^m-1)+(2^n+1) 得出
s | 2^m*(2^(n-m)+1)
得出 s | 2^(n-m)+1. 也就是 n 可以换成 n-m。 直至小于 m。

现在开始数学归纳法。 m = 1 显然正确。 m=3 也正确， 因为 2^3-1=7, GCD(7,1)=GCD(7,3)=1.

假设命题对 m <= 2*k+1 的偶数和任何正整数 n 成立。 令 m = 2*k+3, n<m.

s|2^m-1, s|2^n+1 推出 s | (2^(m-n)+1).

从 s|2^n+1 和 s | (2^(m-n)+1) 推出 s|（2^n+1）-(2^(m-n)+1)

也就是 s | 2^n*(2^(m-2*n)-1） 或者 s | 2^（n-m)*(2^(2*n-m)-1）.

于是 s | 2^(m-2*n)-1 或者 s | 2^(2*n-m)-1

m-2*n 和 2*n-m 都是偶数， 都小于等于 2*k+1.

根据归纳法假设， s=1. 于是命题对 m = 2*k+3 也成立。

根据归纳法原理， 命题对所有偶数 m 成立。

锟斤拷锟洁辑时锟斤拷: 2023-08-31 13:48:34