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

Help needed

  1. Feb 22, 2007 #1
    i want to prove that for every positive integer k, we can find such a positive integer n, such that k divides n and n is only composed of the digits 0 and 3. i don't have any idea how to approach this problem. any help will be appreciated.

    thanks in advance.
     
  2. jcsd
  3. Feb 22, 2007 #2
    Try the numbers below 10 to begin with.
     
  4. Feb 22, 2007 #3

    uart

    User Avatar
    Science Advisor

    Well, as it turns out it can be verified for all the numbers 1..9, but what does that prove?

    1*3 = 3
    2*15 = 30
    3*10 = 30
    4*75 = 300
    5*6 = 30
    6*5 = 30
    7*429 = 3003
    8*375 = 3000
    9*37 = 333
     
  5. Feb 22, 2007 #4

    uart

    User Avatar
    Science Advisor

    --Ignore--
     
    Last edited: Feb 22, 2007
  6. Feb 23, 2007 #5
    but how does that help in proving it for every positive integer k?
     
  7. Feb 23, 2007 #6
    Have you seen any patterns or processes that might be useful?

    If not extend up to 20 or 30
     
  8. Feb 24, 2007 #7
    maybe i'm incredibly stupid but i still don't see any pattern.
     
  9. Feb 24, 2007 #8

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Start with the case when k is a prime number (and not equal to 2 3 or 5).

    Think about the remainders when 3, 30, 300, 3000 ... are divided by k.
     
  10. Feb 26, 2007 #9
    i tried upto 20. but still i can't see any pattern.
    10*3 = 30
    11*3 = 33
    12*25 = 300
    13*231 = 3003
    14*2145 = 30030
    15*2 = 30
    16*1875 = 30000
    17*19590 = 333030
    18*185 = 3330
    19*1737 = 33003
    20*15 = 300

    can anybody please tell me how to prove it for every positive integer k?
     
  11. Feb 27, 2007 #10
    How did you get these results?
    Have you checked them out with what alephzero said?
     
  12. Feb 27, 2007 #11
    yeah i did. but i am still in the dark.
     
  13. Feb 27, 2007 #12

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Actually my comment about k being a prime turned out to be irrelevant, after a bit more thought.

    Consider the sequence 3, 30, 300 ... 3*10^n ... mod k.

    There are a finite number of different values of the sequence.

    So working through the terms in order, after searching a finite number of terms either we find a term = 0, or we find two different terms with the same nonzero value, r say.

    If we find a zero term, we have a value of n. In the other case,

    there exist integers a, b such that a < b and 3*10^a = 3*10^b = r mod k

    Clearly q = 10^(b-a) = 1 mod k

    Now construct a number n such that n = 0 mod k, using a and q. Hint: one such number contains k 3's.
     
    Last edited: Feb 27, 2007
  14. Feb 28, 2007 #13
    Sorry AlephZero, don't think this works for all k, but the method is worth pursuing

    k = 22

    3*10^1 = 8 mod 22
    3*10^3 = 8 mod 22

    q=10^(3-1) = 10^2 = 12 mod 22

    3 = 7*0 +3 <<<<<<
    30 = 7*4 + 2
    300 = 7*42 + 6
    3000 = 7*428 + 4 <<<<<<<<<
    30000 = 7*4285 + 5

    3 + 4 = 7

    3000 + 3 = 7*428 + 4 + 7*0 + 3 = 7*429

    3 = 3 mod 17
    30 = 13 mod 17 <<<<<
    300 = 11 mod 17
    3000 = 8 mod 17 <<<<<
    30000 = 12 mod 17 <<<<<<
    300000 = 1 mod 17 <<<<<<<
    3000000 = 10 mod 17
    30000000 = 15 mod 17
    300000000 = 14 mod 17
    3000000000 = 4 mod 17
    30000000000 = 6 mod 17

    13 + 8 + 12 + 1 = 34 = 0 mod 17

    so

    333030 = 0 mod 17

    So out of the finite list of 3*10^n mod k is it always possible to find a set that adds up to 0 mod k?
     
    Last edited: Feb 28, 2007
  15. Feb 28, 2007 #14

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Oops! Try again...

    Let a < b and 3*10^a = 3*10^b = r mod k.

    Let n = 3*10^a + 3*10^(a+1) + .... + 3*10^(b-1)

    (10 - 1)n = 3*10^b - 3*10^a

    9n = 0 mod k.

    So most of the time, n = 0 mod k

    .... but what happens if k is a multiple of 3 or 9, I wonder.

    EDIT: Lookat what happens for k = 81.
     
    Last edited: Feb 28, 2007
  16. Feb 28, 2007 #15

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    OK, I got it. First, prove the following:

    1 + 10^a + 10^2a is divisible by 3, for any integer a > 0.

    1 + 10^a + 10^2a = (10^3a - 1)/(10-1)
    = (1000^a - 1)/9
    = ((3*9*37 + 1)^a - 1)/9
    Expand by the binomial theorem: the two "1" terms cancel out, and all the other terms are divisible by 3.

    Now the main proof:

    If k is not a multiple of 3, the previous post shows how to construct a number n with 9n = 0 mod k. Since 3 does not divide k, then n = 0 mod k.

    If k is a multiple of 3, let k = 3m.
    Construct a number q such that q = 0 mod m. (Note, this is a recursive algorithm, since m may be a multiple of 3.)

    Let q = r mod 3m. If r = 0 we are done and n = q.

    If r is not 0, then define n to be the digits of q "repeated" three times (for example if q = 30033, n = 300333003330033)

    n = 3r mod 3m, and r = 0 mod m, therefore n = 0 mod 3m.
     
  17. Feb 28, 2007 #16
    AlephZero look back at your first attempt and extend a and b

    The will be (at least) k integers n(i) 1<= i <=k and n(i) =/= n(j) for i=/=j such that 3*10^n(i) = r mod k

    Sum these for i=1 to k and the result, n, will be 0 mod k

    3*10^n(i) = k*m(i) + r for some m(i) 1<= i <=k

    let m be sum of m(i) i=1 to k

    n = km + kr

    n = k(m + r)
     
  18. Mar 2, 2007 #17

    uart

    User Avatar
    Science Advisor

    Good proof jing. So just summarizing, you're saying the Aleph's post should have gone some like as follows :


    Consider the sequence 3, 30, 300 ... 3*10^n ... mod k.

    There are a finite number (k) of different values of the sequence.

    So working through the terms in order, after searching k(k-1) terms either we find a term = 0 (mod k), or we can find at least k terms with the same nonzero (mod k) value, r say.

    If we find a zero term, we have a value of n. In the other case, we can add the k terms with value r to get the required n, as kr = 0 mod k.
     
    Last edited: Mar 2, 2007
  19. Mar 2, 2007 #18
    Thank you uart. I hope it helped murshid_islam to see that when you do not know how to start you just start anyway and play around with some numbers to get a feel of what might be useful. Even if where you start leads you down a dead end it might well have taken you passed the right route. You just have to be open to looking for it.
     
  20. Mar 2, 2007 #19
    1 + 10^a + 10^2a = (10^3a - 1)/(10-1)

    How did you get this?
    A counter example is a=2
     
  21. Mar 2, 2007 #20

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    DOH.....

    [tex]1 + 10^{a} + 10^{2a} = (10^{3a} - 1)/(10^a-1)[/tex]

    Which makes a hash of the rest of the proof, though the result IS valid.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help needed
  1. Need Help! (Replies: 1)

  2. Need help (Replies: 8)

  3. Simplify f(x)/g(x) (Replies: 1)

  4. Need help (Replies: 6)

Loading...