1, 11, 111, 1111 ....

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

 (Easter Holiday gives me another excuse to be lazy....)

A simple number theory question: Show that there is at least one (and hence infinitely many) multiples of p among 1_b, 11_b, 111_b, 1111_b, 11111_b,... for all but finitely many prime numbers p. Here 11111_b etc are numbers written with base b numerals.

Answer after the good-looking easter eggs :P








Let n(k)=111...1_b denote the number with k 1's. Note that
n(k)=$b^{k-1}+b^{k-2}+b^{k-3}+\cdots+1$=(b^k-1)/(b-1).

We claim that when p is not a factor of b, then n(k) is a multiple of p for some k.

Use factor theorem, we know that $x^{k-1}+x^{k-2}+x^{k-3}+\cdots+1=(x-1)q(x)+k$. Consequently, n(k)=k mod (b-1). Therefore if p is a factor of b-1 (and hence not a factor of b), then p divides n(b-1).

By Fermat's little theorem, we know that if p is not a factor of b, then p divides b^p-1-1. Therefore if p is neither a factor of b nor a factor of b-1, then p divides n(p-1).

The claim is proved. Please note that if n(k) is a multiple of p, then so is n(2k), n(3k), and so on.