# Homework Help: Larson problem

1. Jan 2, 2008

### ehrenfest

[SOLVED] larson problem

1. The problem statement, all variables and given/known data
Note: sorry to Loren Larson for constantly misspelling your last name as "larsen" and sorry to everyone who has been wondering who Loren Larsen is.

Given an integer n, show that an integer can always be found that contains only the digits 0 and 1 (in the base 10 notation) and which is divisible by n.
2. Relevant equations

3. The attempt at a solution
I checked this for n=1,2,3,4,5,6,7 and found

1*1=1
2*5=10
3*37=111
4*20=100
5*2=10
6*185=1110
7*143=1001

I think those are the lowest. I fail to see any pattern. I am trying to use the fact that

$$n= \sum_i^{ \left\lfloor \log_{10}(n) \right\rfloor}c_i 10^i$$

where c_i is between 0 and 9 inclusive, but I don't see how that will help me construct a number where c_i = 0 or 1. This chapter is called modular arithmetic, so the solution probably uses mods somehow. Maybe I can use the Chinese Remainder Theorem somehow because I just need to show that this integer exists...

2. Jan 3, 2008

### Dick

There was a thread on this recently in the forum with the title "Fun Divisibility Problem". But you recently proved any group of n+1 numbers contains two whose difference is divisible by n, right? Consider the n+1 numbers, 1,11,111,1111,11111, etc.

3. Jan 3, 2008

### ehrenfest

That's obviously true, and I see how that solves the problem. I don't remember starting a thread on that topic, though.

Last edited: Jan 3, 2008
4. Jan 3, 2008

### Dick

Well, you've posted similar enough problems that the proof ought to be a piece of cake.