1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Number theory - prove if divisible by 2009

  1. Jan 6, 2010 #1
    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 :confused:

    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
    Thanks in advance!
  2. jcsd
  3. Jan 6, 2010 #2
    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.
  4. Jan 6, 2010 #3
    Thank you, rasmhop! I understand now how to get it, your reply was helpful, cheers!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook