- #1
ehrenfest
- 2,020
- 1
[SOLVED] larson problem
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.
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
[tex] n= \sum_i^{ \left\lfloor \log_{10}(n) \right\rfloor}c_i 10^i [/tex]
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...
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
[tex] n= \sum_i^{ \left\lfloor \log_{10}(n) \right\rfloor}c_i 10^i [/tex]
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...