作业帮 > 数学 > 作业

关于数论的一个小问题如果一个数只有0和1组成现在要求一个数是N的倍数的最小值这个数现在比如说是100 对N求余 余数为r

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/11 15:33:58
关于数论的一个小问题
如果一个数只有0和1组成
现在要求一个数是N的倍数的最小值
这个数现在比如说是100 对N求余 余数为r 那么这个数的下面那个数是1000或者是1001
现在问题就是100后面那个数对N求余 余数=(r*10+1 or 0)%N?
解释下为什么是这个呢
题:求N的0-1型倍数(仅由0和1构成的)中的最小者.
指定一个数x,如x=100,100==r mod N,
则1000==10r modN,1001=10r+1 mod N
很明显啊.
大于x的0-1型数是10x,或者10x+1
譬如数列:
1,
(10;11),
((100,101);(110,111)),
(((1000,1001),(1010,1011));((1100,1101),(1110,1111))),
.
取其中某个数x,x==r mod N
于是
10x==10r mod N
10x+1==10r+1 mod N
合写的话,就是10x+(0or1)==10r+(0or1) mod N