Theorem
Prove that for any positive integer \(n\) there exists a positive multiple of \(n\) having at most \(n\) decimal digits whose digits consist exclusively of zeros and ones.
Solution
List out all the repunits having at most \(n\) digits \[ 1\quad 11\quad 111\quad \dotsc\quad \underbrace{111\!\dotsb\!111}_{n\text{ digits}} \] and consider these numbers modulo \(n.\) If any one of these is congruent to zero modulo \(n\) then that will be the multiple we seek. Otherwise, if not, by the pigeonhole principle there must be two of these repunits \(A\) and \(B\) that fall into the same congruence class modulo \(n.\) The number \(|A-B|\) then will be congruent to zero modulo \(n,\) and will be the multiple that we seek.
Putnam & Beyond
The number \(2^{29}\) has only nine distinct digits. Without using a calculator, which digit is missing?
Solution
The sum of its decimal digits of an integer, when divided by nine, will have the same remainder as the integer itself when divided by nine.
Consider a positive integer \(n\) expressed as a decimal number \[ n = a_k 10^k + a_{k-1} 10^{k-1} + \dotsb + a_1 10^1 + a_0 10^0 \] where \(a_i \in \left\{0,1,2,\dotsc,9\right\}.\) Noting that \(10^M \equiv 1 \pmod 9\) for any positive integer \(M,\) \[ n \equiv a_k + a_{k-1} + \dotsb + a_1 + a_0 \pmod 9\,. \] I.e. the number that is the sum of the decimal digits of \(n\) and the number \(n\) itself must reside in the same congruence class modulo \(9.\)
Now since \( 2^{29} = 2^{2+3\times 9} \equiv -4 \pmod 9\,, \) the sum of its nine distinct digits must also be congruent to \(-4\) modulo nine. However \(0+1+2+3+4+5+6+7+8+9 = 45 \equiv 0 \pmod 9\,,\) so the single digit that must be missing, the digits that must be subtracted from this sum, is \(4.\)