Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Larson problem

  1. Jan 2, 2008 #1
    [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


    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...
  2. jcsd
  3. Jan 3, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Jan 3, 2008 #3
    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
  5. Jan 3, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    Well, you've posted similar enough problems that the proof ought to be a piece of cake.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook