Solving the Larson Problem: Constructing 0 & 1 Divisible Integers

[ehrenfest]

[SOLVED] larson problem

Homework Statement

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.

Homework Equations

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

 

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

 

[ehrenfest]

But you recently proved any group of n+1 numbers contains two whose difference is divisible by n, right?

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

 

[Dick]

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