Question

对于任意正整数n，都能找到一个n的倍数，它全都由0和1组成？

如何证明

Answer 1

举个例子，令n=3

这时考虑4个数，1，11，111，1111
其中
1/3余数为1
11/3余数为2
111/3余数为0
1111/3余数为1
由于3的余数只有0，1，2共3种可能，当我们对4个不同的数字取3的余数时，根据鸽巢原理，必然有两个数字a，b的余数相等，那么b-a即为3的倍数，且b-a只由0或1构成

该方法可以推广到任何正整数n上，只要对1到11...1(n+1位)共n+1个数字分别取n的余数即可