如何证明对任意自然数k，存在恰含k个1的0-1数可被k整除？
这个问题用鸽巢原理就能轻松解决，不用复杂的构造技巧，核心思路是利用余数的有限性来锁定符合条件的数。
第一步：用鸽巢原理找到一个含t个1的可被k整除的数（t ≤k）
首先，考虑一系列全1数：( R_1 = 1 ), ( R_2 = 11 ), ( R_3 = 111 ), ..., ( R_{k+1} = \underbrace{111...1}_{k+1个1} )。
这些数除以k的余数只能是0到k-1之间的整数，总共k种可能。但我们有k+1个数，根据鸽巢原理，必有两个数的余数相同。假设这两个数是( R_p )和( R_q )（p > q），那么它们的差：
[
R_p - R_q = \underbrace{111...1}{p-q个1}\underbrace{000...0}{q个0}
]
这个数能被k整除（余数相同的两个数相减，差必然是k的倍数），而且它恰好包含( t = p-q )个1（t ≤k，因为p ≤k+1，q ≥1）。
第二步：从t个1的数构造出k个1的数
现在我们有了一个含t个1且能被k整除的数，接下来分两种情况处理：
- 如果t = k：那( R_p - R_q )就是我们要找的数，直接搞定。
- 如果t < k：我们基于这个t个1的数，构造出恰好k个1的数。
首先，设( k = d \times k' )，( t = d \times m )，其中( \gcd(m, k') = 1 )（d是k和t的最大公约数）。因为( R_p - R_q = 10^q \times R_t )（( R_t )是t个1的数）能被k整除，而10^q和k'（k去掉所有2、5因子后的部分）互质，所以( R_t )必然能被( k' )整除。
由于( \gcd(10, k') = 1 )，根据欧拉定理，存在整数s使得( 10^s ≡ 1 \pmod{k'} )。而( R_t = \frac{10^t - 1}{9} ≡ 0 \pmod{k'} )，说明( 10^t ≡ 1 \pmod{k'} )，即t就是满足条件的s。
现在构造数：
[
X = \underbrace{111...1}{t个1}\underbrace{000...0}{t个0}\underbrace{111...1}{t个1}\underbrace{000...0}{t个0}...\underbrace{111...1}_{t个1}
]
也就是把t个1的数重复k'次，每次之间用t个0隔开。这个数恰好有( t \times k' = d \times m \times k' = k )个1（因为k = d×k'）。
最后验证X能被k整除：
- 因为( 10^t ≡1 \pmod{k'} )，X可以写成( R_t \times (1 + 10^t + 10^{2t} + ... + 10^{(k'-1)t}) )，括号里的每一项模k'都等于1，总和是k'，而k'是k的因子，所以整个式子模k'等于0。
- 对于k中包含的2和5的因子，我们只需要给X乘以( 10^s )（s是k中2和5的最大指数，比如k=20=2²×5，s=2），这样X×10^s末尾会有s个0，能被2²×5整除，同时1的数量还是k个。
这样X×10^s就是一个恰好包含k个1、能被k整除的0-1数。
举个实际例子
比如k=4：
- 第一步找t个1的数：R1=1（余1），R2=11（余3），R3=111（余3），取R2和R3，差是111-11=100，这个数有1个1，能被4整除（100÷4=25）。
- t=1，k=4，d=gcd(1,4)=1，k'=4，m=1。构造X=1010101（4个1，间隔1个0），乘以10^2（因为4=2²，s=2）得到101010100，这个数有4个1，除以4得25252525，确实是整数。
当然实际中也有更简单的数，比如111100（4个1，111100÷4=27775），但我们的证明保证了对任意k都存在这样的数。
内容的提问来源于stack exchange，提问作者user536095
