Friday, April 5, 2013

1, 11, 111, 1111 ....

If you are in Hong Kong and you need help for university mathematics courses, please visit

 (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 1b, 11b, 111b, 1111b, 11111b,... for all but finitely many prime numbers p. Here 11111b etc are numbers written with base b numerals.

Answer after the good-looking easter eggs :P

Let n(k)=111...1b denote the number with k 1's. Note that

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 bp-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.