注明: 符号 | 是“整除”的意思
命题: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 成立。
命题: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