Primes in an Infinite Set

85 Views Asked by At

Let $S$ be the infinite set of positive integers whose members can be written with no digits except $0$ and $1$ and with no more than $1988$ $1s$. Show that some integer $n$ does not divide any member of $S$

(Tournament of the towns 1st half of 1989 Senior A level)

1

There are 1 best solutions below

0
On BEST ANSWER

For $y=1998$ choose $m>\lfloor y/9\rfloor=220$; then $n=10^m-1$ does not divide the sum of any $k$ powers of$~10$ for $0<k\leq y$, which is the property you want. (One does not need to suppose the powers of ten distinct, so $n$ will more generally not divide any positive number whose sum of digits is at most $y$.)

To see that this is true, note first that $10^a\equiv10^r\pmod n$ when $a\equiv r\pmod m$. So replacing exponents by their remainders modulo $m$, it suffices to prove this for sums of terms among $1,10,100,\ldots,10^{m-1}$. Moreover such a sum in which one same term occurs at least $10$ times can be reduced to a sum with fewer terms by combining those terms, so one may assume that this does not happen. But all remaining sums of powers of $10$ give a positive result less than $n$, so not divisible by $n$.