Problem
NT-B1-M12-P018 Set 4. Multiple with Zeros and Ones
#18
★★★☆☆ Level 3 of 5
Let \(\gcd(m,10)=1\). Prove that there exists a number consisting only of digits \(0\) and \(1\) that is divisible by \(m\).
It is enough to construct a number of only ones.
By the pigeonhole principle, among \(R_1,\ldots,R_m\), either one is divisible by \(m\), or two have the same residue. In the second case their difference is \(10^iR_j\) for some \(j\) and is divisible by \(m\). Since \(10^i\) is invertible modulo \(m\), \(m\mid R_j\). The number \(R_j\) consists only of ones, hence only of digits \(0\) and \(1\).
Constructive problem without an explicit number.