# Homework Help: Number theory - prove if divisible by 2009

1. Jan 6, 2010

### DianaSagita

1. The problem statement, all variables and given/known data

Prove if there exists an integer whose decimal notation contains only 0s and 1s, and which is divisible by 2009.

2. Relevant equations

Dirichlet's box principle

3. The attempt at a solution

I'm new to number theory, and I'm aware that I do not have the proper reasoning for this, but tried:
10^n + a[n-1]*10^(n-1) + ... + a[0] = k* (2*10^3 + 9), where a={0,1}

tried to find k with the max power of 10^(n-1), but it seems my approach is wrong... :( please help

2. Jan 6, 2010

### rasmhop

Consider numbers of the form 1, 11, 111, 1111, ... According to the box principle at some point two members of this sequence will be equal modulo 2009. In that case subtract the smaller from the larger and you should get your integer.

3. Jan 6, 2010

### DianaSagita

Thank you, rasmhop! I understand now how to get it, your reply was helpful, cheers!