Pages

Monday, August 17, 2009

KBB2 Problem 6

An integer is called homogenous if its decimal representation consists of 1 number. For example, 11 and 222 are homogenous. Prove that there are infinitely many homogeneous numbers that are divisible by 2008.

Solution


We will show that for any $k$, the number 888...8 ($250k$ 8's) is divisible by 2008.

Since 2008 is $8 \times 251$ and 251 is prime, then according to Fermat's Little Theorem:

$10^{250} \equiv 1 \mod 251$

So $10^{250k} \equiv 1 \mod 251$ for any $k$, which means there is an $n$ such that

$10^{250k} - 1= 251n $

The LHS is divisible by 9, thus so is the RHS. Because 251 is prime, then $n$ is divisible by 9. Suppose $n = 9m$, then

$\displaystyle \frac{10^{250k} - 1}{9} = 251m$

$111...1 = 251m$ where there are $250k$ ones.

Thus, $888...8 = 2008m$.

No comments:

Post a Comment