求证：若n不被2或5整除，则存在全1数可被n整除（附困惑）

嘿，这个问题用鸽巢原理来解决就非常直观啦！你之前从n的十进制展开入手的思路可能绕远了，换个角度来梳理：

第一步：定义全1数的表达式 #

先定义一串由k个1组成的正整数：
$$R_k = \underbrace{111...1}_{k个1}$$
这个数可以用幂次形式简化表示：$R_k = \frac{10^k - 1}{9}$——毕竟$10^k - 1 = 999...9$（k个9），除以9就得到k个1的数，这个转换是解题的关键。

第二步：用鸽巢原理找余数重复的情况 #

考虑这$n+1$个全1数：$R_1, R_2, ..., R_{n+1}$。每个数除以n时，余数的可能取值只有0到n-1这n种情况。根据鸽巢原理，这$n+1$个数里至少有两个数除以n的余数相同，假设这两个数是$R_i$和$R_j$（不妨设$i > j$）。

第三步：构造能被n整除的全1数 #

既然$R_i$和$R_j$除以n的余数相同，那么$R_i - R_j$一定能被n整除。我们来展开计算这个差值：
$$
\begin{align*}
R_i - R_j &= \frac{10^i - 1}{9} - \frac{10^j - 1}{9} \
&= \frac{10^i - 10^j}{9} \
&= 10^j \times \frac{10^{i-j} - 1}{9} \
&= 10^j \times R_{i-j}
\end{align*}
$$

题目里明确n不被2或5整除，这意味着n和10是互质的（$\gcd(n,10)=1$），自然$10^{j$和n也没有公共因数。因为$n$整除$10}j \times R_{i-j}$，且n与$10^j$互质，所以n必须整除$R_{i-j}$——而$R_{i-j}$正是一个由$i-j$个1组成的正整数！

这样我们就完成了证明～你之前的思路没用到互质性和鸽巢原理，所以才卡住，换这个方向就顺畅多了。

内容的提问来源于stack exchange，提问作者user466946