17 太复杂了,为什么不能够直接这样呢?
这个"证明"是最简单的,并且小学生都会.这么小的数别搞那些花里胡哨的.
[有人对我用公式编辑器的长除法不满意啊,其实我自己也不满意啊.不怪我,要怪就怪知乎的公式编辑器太落后了,长除符号不支持.对了,如果要完美地用公式表示,知乎还得支持对齐符号,之前那个公式我就使用了(在里),但是放知乎却诡异般偏移,对了我还是用的 14 阶方阵凑成的.现在用PS重新改成图片式的了,用了钢笔(贝塞尔曲线)+直线,花了大概 4 分钟来弄吧]
另外,有人认为这个不是证明.我上面的["证明"]加双引号的意思是,这个还缺论证 4 是余数的最后步骤,只是没用语言描述这个余数就是 4 而已.而上面的证明步骤已经完成到最后一步了.只需加上:由上长除法得, div17 的余数为 4 ,因此命题得证.
这可不是不算证明.因为余数定义正是: [n = qm + r,left( {n,q,m,r in {N},0 r < m} right)] 的 r ,而长除法是构造性地得到 q,r ,这个证明基本高代里,初等数论里都有这样的证明,具体不展开.
因此,通过长除得到的结果肯定是证明!
花哨的运算量不会比长除法少,因为 这个数还是太小了,如果要用花哨解法,起码几十,几百或者几千位.那样的运算量才会显著减少,但这里,首先对除数 17 进行分析.分析的步骤可能都及得上上面那样的运算,这还只是个开头:仅仅只是对 17 的余数结构的分析!所以非要花里胡哨是不值得的.
首先说下几个重要的性质(下文的整数不做特别说明都指代正整数):
[1]同余三则运算法则(这里包括负数,即指全部整数.):
[begin{} a equiv bleft( {bmod m} right),c equiv dleft( {bmod m} right) hfill left{ begin{} a pm b equiv c pm dleft( {bmod m} right) hfill ac equiv bdleft( {bmod m} right) hfill end{} right. hfill end{} ]
[2]欧拉 phi 函数:
[phi left( n right) = nprod{p|n} {left( {1 - frac{1}{p}} right)} ] ,(其中的 p 都是指素数)为 left{ 1,...,n right} 以内与 n 互质的整数的个数( 1与任何整数互质).
对于欧拉 phi 函数有欧拉定理:任意互质的两个整数 a,m 都有 [{a^{phi left( m right)}} equiv 1left( {bmod m} right)]
[3]整数的阶:
定义 [{{ord} _n}a] 是使得 [{a^x} equiv 1left( {bmod n} right)] 成立的最小整数 x ,称为模 n 的 a 的阶.对于此有定理: [{{ord} _n}a|phi left( n right)] .
然后我们利用以上定理来推论除以 17 的余数系统:
首先 17 是一个素数,因此根据欧拉定理得:
[{10^{16}} equiv 1left( {bmod 17} right)]
注意到 16 的素因数只有 2 ,所以考虑数 [2,4,8,16] (这些数都是 16 的因数):
另外注意到 17=17div2=85
[begin{} {10^2} equiv 17 times 5 - 70 equiv 15 equiv - 2left( {bmod 17} right) hfill {10^4} equiv {10^2} times {10^2} equiv 4left( {bmod 17} right) hfill {10^8} equiv {10^4} times {10^4} equiv 16 equiv - 1left( {bmod 17} right) hfill {{ord} _{17}}10 = 16 hfill end{} ]
由于 长度为 11left( ,因此我们需要把 [left{ {{{10}^0},{{10}^1},...,{{10}^{10}}} right}] 的余数求出(如果 [{{ord} _{17}}10 = 2,4,8] 就可以缩短需要求的余数量)
我们可以用乘法同余法则并同时考虑正负整数:
[begin{array}{*{20}{l}} {{{10}^1} equiv 10 - 17 equiv - 7left( {,bmod ,17} right)} {{{10}^2} equiv - 2left( {,bmod ,17} right)} {{{10}^3} equiv {{10}^2} times {{10}^1} equiv left( { - 2} right) times left( 7 right) equiv 14 equiv - 3left( {,bmod ,17} right)} {{{10}^4} equiv 4left( {,bmod ,17} right)} {{{10}^5} equiv {{10}^2} times {{10}^3} equiv left( { - 2} right) times left( { - 3} right) equiv 6left( {,bmod ,17} right)} {{{10}^6} equiv {{10}^3} times {{10}^3} equiv left( { - 3} right) times left( { - 3} right) equiv 9left( {,bmod ,17} right)} {{{10}^7} equiv {{10}^4} times {{10}^3} equiv 4 times left( { - 3} right) equiv - 12 equiv - 12 + 17 equiv 5left( {,bmod ,17} right)} {{{10}^8} equiv - 1left( {,bmod ,17} right)} {{{10}^9} equiv left( { - 7} right) times left( { - 1} right) equiv 7left( {,bmod ,17} right)} {{{10}^{10}} equiv left( { - 2} right) times left( { - 1} right) equiv 2left( {,bmod ,17} right)} end{array}]
这样考虑十进制展开并通过乘法和加法同余法则得到:
[begin{array}{l} equiv left{ {begin{array}{*{20}{r}} 1&2&3&4&5&6&7&8&9&2&3 2&7&{ - 1}&5&9&6&4&{ - 3}&{ - 2}&{ - 7}&1 end{array}} right. equiv 2 + 14 - 3 + 20 + 45 + 36 + 28 - 24 - 18 - 14 + 3 equiv 4left( {bmod 17} right) end{array}]
其中的大括号后面的两层数表示分别上下对应相乘并相加(相当于向量数量积)
你看到没,这个判断起来需要花费长除法大概两倍的运算量.其次,这个所做的只是看起来像是把除法的处理变成乘法和加法的处理罢了.因为 的长度小于 16 又接近 16 .而且 17 并不是 [2,3,5,7,11,13] 这种素数.这就说明它并不那么"好".
(1)对于 [2,5] ,他们是 10 的因数,因此求对于 2^n 或 5^n 的余数只需要考虑从个位数开始的前 n 位数即可.
例:
求 [ div {2^5}] 的余数.由以上说明,我们只需要取从个位数开始的前 5 位:
即 [ div {2^5}] 的余数等于 [30216 div {2^5}] 的余数.注意到 2^5=32 .使用长除法即可得到其余数为 8 ,也即 [ div {2^5}] 的余数为 8 .
同理:求 [ div {5^5}] 的余数等于 30245div5^5 的余数,因此是 2120 .
(2)对于 3,9 ,只需考虑把每一位的数字相加起来的和即可.
例:求 [{rm{div3}}] 以及 div9 的余数.
等于 [left( {{rm{8 + 1 + 3 + 2 + 9 + 1 + 6 + 9 + 8 + 0 + 3 + }}...{rm{9 + 4 + 0 + 8 + 9}}} right) div 3] 或者 div9 的余数.因此分别是 2,5
(3)对于 7,11,13 只需考虑从个位数开始的每 3 位为一组数(拆成至多三位数)交错相加(第一组为正,下一组改变正负性)的和即可.
例:求 [] 分别除以 7,11,13 的余数:
首先(从个位数开始)分割成三位,三位一组:
[001|021|106|068|594|697|946|551|788|765|918|277|778|334|185|399|873]
从个位数(那一组)开始,依次交错相加:
[873 - 399 + 185 - 334 + 778 - 277 + 918 - 765 + ... - 068 + 106 - 021 + 001 = ]
[ = 2077]
由长除法得:
[begin{array}{l} 2077 div 7 = 296 cdots cdots 5 2077 div 11 = 188 cdots cdots 9 2077 div 13 = 159 cdots cdots 10 end{array}]
这些余数就是原来的数所对应的余数,另:商当然不相等.
(4)而对于除此之外的可以由这些数作为因数组成的合数(由于这些数互质 [left{ {{2^n},left( {3或9} right),{5^n},7,11,13} right}] )可以利用孙子定理,通过分别对这些因数求余后,再由孙子定理得到总的(该合数的)余数.
例:
求 [ div 576] 的余数.
注意到: [576 = 9 times 64 = 9 times {2^6}]
首先分别求得上数除以 9 的余数为 0 ,而除以 2^6 的余数为 14 .
由孙子定理得:
[x equiv 0 + 14 times 9 times Mleft( {bmod 576} right)] ,其中 [9M equiv 1left( {bmod {2^6}} right)]
一般来说,可以通过欧几里得算法或者欧拉定理并利用快速指数幂求 M .
这里提供欧几里得算法:
[begin{array}{l} 64 = 9 times 7 + 1 9 = 1 times 9 + 0 end{array}]
所以 [1 = 64 times 1 - 9 times 7,9left( { - 7} right) equiv 1left( {bmod 64} right)]
[begin{array}{l} x equiv 14 times 9 times left( { - 7} right)left( {bmod 576} right) x equiv - 882 equiv 576 times 2 - 882 equiv 270left( {bmod 576} right) end{array}]
所以 [ div 576] 的余数为 270 .
但 17 都不是这些数!这样,我们不论怎样做都是有点复杂的,这包括我们直接使用长除法.
另外给出另一位答主所提供的求法的详细原理,它基于一个定理,学过数论的话这个定理是非常显然的:
[4]定理:设 [n = 10b + a] ,除以 m 的余数( m 与 10 互质)模 m 下的 e 倍等于 b+ae 除以 m 的余数.(这个 e 称为 10 模 m 的逆。而逆是指使得 [10e equiv 1left( {bmod m} right)] 成立的 e )
[感谢 @李宁远 指出,原句是后面 b+ae 除以 m 的余数模 m 下的 e 倍,这个 b+ae 的余数已经在原基础上乘了 e 了,这个说法是错误的.我是很后来才注意到的,发现读着不顺才注意到这个逻辑关系]
特别的, m 是 n 的因数当且仅当 [n div m] 的余数与 [left( {b + ae} right) div m] 的余数相同(即为0).
另外,如果考虑 a 为个位数,而 b 就是十位数以上的,那么我们可以通过这样反复迭代:
[begin{array}{l} n equiv xleft( {bmod m} right) 10b + a equiv xleft( {bmod m} right) b + ae equiv xeleft( {bmod m} right) 10b' + a' equiv xeleft( {bmod m} right) b' + a'e equiv x{e^2}left( {bmod m} right) ... end{array}]
这样记第 k 次执行后的 b 与 a 为 b_k 与 a_k .即也即有:
[{b_k} + {a_k}e equiv x{e^k}left( {bmod m} right)]
(其实这个过程就包含了该定理的证明了).
由欧拉定理得到: [e equiv {10^{phi left( m right) - 1}}left( {bmod m} right)] ,我们现在就来求对于 m=17 的 e :
通过之前的关于 10^n 对 17 的余数的结果,我们就可以得到:
[{10^{phi left( {17} right) - 1}} = {10^{15}} equiv {10^8} times {10^7} equiv left( { - 1} right) times 5 equiv - 5left( {bmod 17} right)]
[补充一点:关于这里的 -5 是可变的还是不可变的,能不能换成 -10?
答:不能随便换,如果要换就要对其加上或减去任意整数倍 17 ,比如 -39,-22,+12,+29 等,都能把 -5 换掉,这个意义是指与 -5 在模 17 下是"相等的"]
所以一个数 n 满足式子 [n = 10b + a]
那么它是否整除 17 等价于 [b - 5a] 是否整除 17 .
用语文角度的描述是:一个数能否整除 17 和一个数截去个位数所留下的数减去原来个位数的五倍的差能否整除 17 同一结果.
如可以这样:
[begin{array}{l} 15345 equiv 1534 - 5 times 5 equiv 1509 equiv 150 - 9 times 5 equiv 105 equiv 10 - 5 times 5 equiv - 15 equiv 2 ne 0left( {,bmod ,17} right) end{array}]
所以 17 不能整除 15345 也即 17 不是 15345 的因数.
(虽然说这里用同余符号是有点问题的,因为如果像上面那样不是 0 ,执行的每一步出现的同余号都是错的,所以这里的同余号有一种在其上面标 ? 的意义在,表示"是否同余".对此要么默认,要么换符号,我这里为了清晰度而更换为" "(不表示趋于))
[begin{array}{l} 15345 to 1534 - 5 times 5 equiv 1509 to 150 - 9 times 5 equiv 105 to 10 - 5 times 5 equiv - 15 equiv 2 ne 0left( {,bmod ,17} right) end{array}]
同理论证 [left( { - 4} right)] 能否被 17 整除.
[begin{array}{l} - 4 = to - 45 equiv left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to - 30 equiv left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to - 20 equiv left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to - 25 equiv left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to - 0 equiv left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to 12345 - 20 equiv 12325left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to 1232 - 25 equiv 1207left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to 120 - 35 equiv 85left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) to 8 - 25 equiv - 17 equiv 0left( {{mkern 1mu} bmod ,{mkern 1mu} 17} right) end{array}]
这是用上述定理(作为整除判断形式)论证 [{div17}] 的余数是 4 ,不过这个使用的前提是你必须知道 4 是余数结果.否则最终得不到 0 ,这我们也就白白浪费时间而只是去检验它是否能被整除!
用完整形式可以构造性地求解原来的数所对应的余数:
[begin{array}{l} equiv xleft( {bmod 17} right) equiv xeleft( {bmod 17} right) equiv x{e^2}left( {bmod 17} right) equiv x{e^3}left( {bmod 17} right) equiv x{e^4}left( {bmod 17} right) equiv x{e^5}left( {bmod 17} right) 12299 equiv x{e^6}left( {bmod 17} right) 1184 equiv x{e^7}left( {bmod 17} right) 98 equiv x{e^8}left( {bmod 17} right) end{array}]
[x{e^8} equiv 98 - 102 equiv - 4left( {bmod 17} right)]
由 [{10^8}{e^8} equiv 1left( {bmod 17} right)]
[ {e^8} equiv - 1left( {bmod 17} right)]
[ x equiv left( { - 4} right){e^8} equiv 4left( {bmod 17} right)]
这是直接利用原定理推论得到.还是那句话,这需要你先前分析过 17 的余数结构,而不像长除法那样不需要考虑.这意味着会有一个"预计算时间".长期来讲,无论是直接考虑 10 进制形式,利用同余性质得到,还是通过 10 的逆的形式,并迭代计算得到.这些都要比长除法好.这应该发生在相当高位,如几十位.对于这边的方法都会将数分成 16 位长一组并分组求以及相加.能够发现这个性质就必须先分析 17 的余数结构,这才是长除法做不到的地方.所以说,不要用花哨的证法,最简单的长除解决之.
发表回复