|
上节课的习题第一题，有些朋友私信问黄老师该如何解答，下面黄老师讲解一下。 题目如下： 此题如何解？黄老师算了一下，发现此题出的过于难了，当时在网上找了个图片未经自己验证就当成习题出了。。。 寻找解题思路如下： 第一感觉：有没有可能利用循环来解，即2^1、2^2、2^3……减1以后除以343的余数是一段循环的数字； 通过简单计算，发现不太可能，因为2^8=256，减1除以343余255，只有9次方以后才可能出现循环，但试验了几个未发现，再者，2^20这个数值大于100万了，计算量太大了，所以，利用循环是解决不了此题的。 那该怎么办？ 我们只能利用余数的相关知识看看能不能解？ 必备知识： 因为147在指数上，所以考虑把147这个数分解因数： 147=3×7×7 所以2^147=2^(3×7×7)=(2^3)^(7×7)或=(2^7)^(3×7) 即： 2^147=8^(7×7)或 2^147=128^(3×7) 上述2式一个是先计算8^7除以343的余数，然后余数的7次方再除以343得到的余数，最后减1； 一个是先计算128^3除以343的余数，然后余数的7次方再除以343得到的余数，最后减1； 两式选一计算即可，黄老师在此都进行计算一下： A：8^7=2097152，2097152÷343=6114……50 50^7=50^3×50^4 50^3÷343=364……148；50^4÷343=18221……197； 再计算：148×197÷343=85……1 所以2^147÷343余1，即（2^147-1）能整除343，余数为0 B：128^3=2097152， 下同A： 2097152÷343=6114……50 50^7=50^3×50^4 50^3÷343=364……148；50^4÷343=18221……197； 再计算：148×197÷343=85……1 所以2^147÷343余1，即（2^147-1）能整除343，余数为0 此方法均为笨方法，能否有更简单的方法呢？ 先不考虑减1，只考虑2^147÷343 因为343=7×7×7 我们知道的是： 求两个数相乘再除以一个数m的余数，可以先计算每个乘数除以m的余数，然后再将余数相乘再除以m。 那么，对于被除数，有类似的性质吗？？ 为此，黄老师做了个验证表： 上图，第一列为指数，第二列为2^n的得数，第三列为该得数减1后得数，第四列为第三列除以7得到的余数，第五列为第三列除以(7×7)得到的余数，最后一列为第三列除以(7×7×7)得到的余数。 由图可见，除以7时，到2^3-1时可以整除，而下几个是2^6-1、2^9-1、2^12-1…… 对应的，除以(7×7)时，第一个是2^21-1，（21是由3×7得到），推理应该得到：第二个能被(7×7)整除的应该是2^42-1：原因是： 2^42-1=（2^21+1）×（2^21-1）（平方差公式） 所以，推出： 除以(7×7×7)时，第一个是2^147-1，（147是由3×7×7得到） 此处缺乏严谨证明，但可以通过引入立方差公式： 及N次方差公式(a^n+b^n=(a+b)(a^(n-1)-a^(n-2)*b+a^(n-3)*b^2-……+a^2*b^(n-3)-a*b^(n-2)+b^(n-1)) (n是奇数）)，来证明 此证明太过烦索，黄老师力所不及，看看有没有朋友可以证明！ 此讲太过复杂，主要因为上一讲黄老师不小心给自己下了个坑，如果哪位大神有更好的解题方法，欢迎指教！ |
|
|
