1. Not finding help here? Sign up for a free 30min 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!

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