证明2^155-1能被961整除.
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/25 12:30:35
证明2^155-1能被961整除.
证明2^155-1能被961整除.
证明2^155-1能被961整除.
首先证明：当n>=1,2^5n-1 可以被31整除,利用数学归纳法：
令K(n) = 2^5n - 1
当n=1：K(1) = 2^5 - 1 = 31
假设：2^5n - 1可以被31整除
那么：K(n+1)
= 2^5(n+1) - 1
= 2^5n * 2^5 - 1
= 32 * 2^5n - 1
= (2^5n - 1) + 31 * 2^5n
= K(n) + 31 * 2^5n
显然,K(n)和31 * 2^5n都可以被31整除,即K(n+1)可以被31整除
由此,当n>=1,K(n)可以被31整除
显然：2^155 - 1 = 2^(31 * 5) - 1 = K(31)
由上面的证明可知,K(31),也就是2^155 - 1可以被31整除
由于：K(n+1) = k(n) + 31 * 2^5n
令a(n) = k(n) / 31
那么：a(n+1) = a(n) + 2^5n
a(1) = K(1) / 31 = 31 / 31 = 1
a(2) = a(1) + 2^5 = 1 + 2^5
a(3) = a(2) + 2^10 = 1 + 2^5 + 2^10
a(n) = a(n - 1) + 2^5(n-1) = 1 + 2^5 + 2^10 + ...+ 2^5(n - 1)
a(31) = 1 + 2^5 + 2^10 + ...+ 2^(5*30)
= 1 + [2^5 - 1] + [2^10 - 1] + ...+ [2^(5 * 30) - 1] + 30
= [2^5 - 1] + [2^10 - 1] + ...+ [2^(5 * 30) - 1] + 31
= K(1) + K(2)+ ...+ K(30) + 31
K(n)可以被31整除,所以
a(31)可以被31整除
由于a(31) = K(31) / 31,所以K(31)可以被31*31 = 961整除
即：2^155-1能被961整除