返回题库

任意自然数都有只含 0/1 的倍数

any natural number has a multiple whose decimal representation

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

证明：任意自然数 nn 都存在一个倍数，其十进制表示只包含数字 0 和 1。

例如 13×77=100113\times 77=1001。

Show that any natural number has a multiple whose decimal representation only contains the digits 0 and 1. For example, if the number is 13, we get 13×77=100113 \times 77 = 1001 .

解析

考虑 n+1n+1 个数：

1, 11, 111, …, 11⋯1⏟n+1 个 1.1,\ 11,\ 111,\ \dots,\ \underbrace{11\cdots 1}_{n+1\text{ 个 1}}.

它们模 nn 的余数只有 nn 种可能：

  • 若其中某个余数为 0，则该数本身就是所求倍数；
  • 否则由抽屉原理，必有两个数同余。用较大的减去较小的，得到一个由若干个 1 后接若干个 0 组成的数（十进制只含 0/1），且它们差仍被 nn 整除。

因此结论成立。

Original Explanation

Consider the n+1_{\mathrm{n + 1}} numbers 1,11,111,1111, etc. Two of them will be congruent modulo n. Subtract the smaller one from the bigger one. You will get a number containing only 0's and 1's.