本帖最后由 平常心 于 2014-1-4 15:48 编辑
对在各种进制下判断数字能否被3整除问题的思考
我们习惯十进制数的简单判断方法,但一般不追究其原因。 其实原因很简单,这是由于10^k≡1(mod3)。这样我们可将10、100、1000……等都看做1,最后将各个数位的数字加起来,若能被3整除,原来的数即可被3整除。 四、七、十三、十六……进制数与十进制数一样,都可以用这个方法。 三、六、九、十二、十六……进制数很明显,可以直接看出。 其他进制数略微麻烦一点,其中二进制数较简单,我们仅以此为例介绍如下: 由于,2^2k≡1(mod3) 2^(2k+1)≡2(mod3) 故: 2^2(k+i)+2^2k+1≡0(mod3) (k∈N, i∈N) 例如:2^4+2^2+1=21; 2^8+2^4+ 1=273; 2^10+2^2+ 1=1029…… 当i=0时,2^2(k+i)+2^2k+1 =2^(2k+1)+1≡0(mod3) 例如: 2^3+1=9; 2^5+ 1)=33; 2^7+1=129…… 将以上二式化作二进制数就是: 10^2(k+i)+10^2k+1≡0(mod11) 10^(2k+1)+1≡0(mod11) 也就是说,以下三类字符串,定可被11(3)整除: ①11、1111、111111……(3、15、63……) ②1001、100001、10000001……(9、33、129……) ③10101,1010001,101000001……100010001……(21、81、321……273) 在此基础上,可进一步推演出更实用的复杂组合: 令:A=00……0(由奇数个连续的0组合的字符串) B=1……1(中间为任意多个字符组合,但不包含A字符串) 任何二进制数均可由0、1与A、B字符串组合而成,其中: 0≡0(mod11) 11≡0(mod11) 1A01≡0(mod11) 1ABA1≡0(mod11) 1≡1(mod11) 1A0≡1(mod11) 1ABA≡1(mod11) 1A≡10(mod11) 1A1≡10(mod11) 1AB≡10(mod11) 1 ABA0≡10(mod11) 对于具体的二进制数,可由左至右逐个划去≡0(mod11)的字符串,由最后剩余的字符串即可确定该数是否可被11(3)整除,或者其余数是几。 例如:10111111001110000111111000011111≡10(mod11) 100111100011001001111000000001111111101≡0(mod11) 10000110001100111110000001111110011000≡1(mod11) |