Tricky?

Discussion in 'Physics & Math' started by Fudge Muffin, Jan 20, 2012.

  1. Fudge Muffin Fudge Muffin Registered Senior Member

    Messages:
    148
    given that 5^j + 6^k + 7^l + 11^m = 2006 (where j,k,l and m are different non-negative integers) what is the value of j+k+l+m?

    i don't even know where to start. Any hints?

    Please Register or Log in to view the hidden image!

     
    Last edited: Jan 21, 2012
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Tach Banned Banned

    Messages:
    5,265
    Hint: start with the fact that m < 4
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. RJBeery Natural Philosopher Valued Senior Member

    Messages:
    4,175
    Here's a start:

    (5%2006)j + (2%2006)k + (4%2006)l + (4%2006)m = 0​

    The '%' operator is for modulus, where (5%2006) = 1 or -4
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Fudge Muffin Fudge Muffin Registered Senior Member

    Messages:
    148
    i know it can be done using simple maths, but not trial and error. what does m<4 imply?
     
  8. Tach Banned Banned

    Messages:
    5,265
    That m can only be {1,2,3}
     
  9. Neddy Bate Valued Senior Member

    Messages:
    1,838
    That is awesome, I never thought of approaching it that way. On the other hand, the use of the term "non-negative" in the OP means that you should also include zero, i.e., {0,1,2,3,}. I haven't worked the problem to know if the zero is required, but I think it should be considered possible.
     
  10. Fudge Muffin Fudge Muffin Registered Senior Member

    Messages:
    148
    Is there any other way rather than trying all the possibilities until i get 2006?
     
  11. prometheus viva voce! Registered Senior Member

    Messages:
    2,045
    Another factoid that may help you is the integer powers of 5,6, and 11 all end with 5,6 and 1 respectively. The powers of 7 end with 1,7,9 or 3 cyclically.
     
  12. Guest254 Valued Senior Member

    Messages:
    1,056
    Oooh, games! Let's see: clearly k=0 (look mod 2) so need to solve 5^j+7^l+11^m=2005. Then we see 2^l+1=0 (mod 5), so l=2 (cant be larger solution otherwise 7^l is too big). Then question is reduced to 5^j+11^m=1956. Now it's easy.
     
  13. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    Nice
     
  14. Fudge Muffin Fudge Muffin Registered Senior Member

    Messages:
    148
    aw... brilliant.

    But I don't follow lol, why must k be 0?
     
  15. CptBork Robbing the Shalebridge Cradle Valued Senior Member

    Messages:
    5,862
    No it ain't. \(5\equiv 5\quad (\mathrm{mod}\ 2006)\).
     
  16. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    As guest says, you use modular arithmetic (all of these sorts of questions use it in some way). He says consider mod 2, which amounts to considering even vs odd.

    If you're unfamiliar with modular arithmetic then check Wiki but the relevant point is that if X = Y mod Z then it means that Z goes into X some whole number of times with Y as the remainder. For example 13 mod 5 is 3 because 5 goes into 13 twice with 3 left over, ie 13 = 5n+3 where n = 2. So in general X = nZ + Y for integer n, which you generally don't care about in these problems.

    The application of this definition is that if X = Y mod Z then for k>0 we have \(X^{k} = Y^{k}\) mod Z (take note that if k=0 then \(X^{k} = 1\), mod or not.The proof is by the binomial theorem but to use the previous example 13 = 3 mod 5. \(13^{2} = 169\) and 169 = 4 mod 5. But \(3^{2} = 9\) and 9 = 4 mod 5. It's much easier to do the modular simplification then raise something to a power than raise it to the power and then do the modular simplification. This way you don't have to compute HUGE numbers for problems (for example, I've seen one where you need to consider \(4444^{4444}\). Your calculator will be useless!). If you have an equation A = B then if you mod both sides you get 'A mod Z = B mod Z', for any choice of Z, which you can use to your advantage, which is what Guest does by taking mod 2 of both sides.

    We note that 5,7,11 are all 1 mod 2 while 6 and 2006 are 0 mod 2. \(5^{j},7^{l},11^{m}\) will all be 1 mod 2, so we we have \(5^{j}+7^{l}+11^{m} = 3 = 1\) mod 2 for any non-negative values of j,l,m, including 0. So now we have \(6^{k} + 1 = 0\) mod 2. But 6 mod 2 = 0. The only way to make \(6^{k} = 1\) mod 2 and make the equation value is to set k=0.

    So we have \(5^{j} + 1 + 7^{l} + 11^{m} = 2006\) and so \(5^{j} + 7^{l} + 11^{m} = 2005\).

    Prom's comment follows similar methodology but can be applied in a different manner.

    /edit

    I don't know if he considered it but just didn't say but Guest's use of mod 5 assumes j>0 so it gives 0 contribution. Just as with k you can consider j=0 but in this case you can exclude it pretty quickly, thus arriving at the place Guest moves on from.
     
  17. Tach Banned Banned

    Messages:
    5,265
    m cannot be 0 because k is already 0
     
  18. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    k=0 doesn't automatically imply m>0. It might well be true (I haven't looked into it in detail) but just because k=0 doesn't immediately and trivially exclude m=0. The mod 2 argument sets k=0 because the only way to alter the value of the left hand side mod 2 is to set k=0 or k>0, since all the odd terms are 1 mod 2, regardless of their non-negative integer powers.
     
  19. Tach Banned Banned

    Messages:
    5,265
    k=0 means \(5^{j} + 7^{l} + 11^{m} = 2005\) which does not accept m=0 as a solution because it will imply \(5^{j} + 7^{l} = 2004\).
    You must have k=0 and this rules out m=0.
     
  20. Fudge Muffin Fudge Muffin Registered Senior Member

    Messages:
    148
    SORRY the question also states that that j,k,l and m are DIFFERENT non-negative integers.

    This probably makes it easier...
     
  21. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    I don't deny that k=m=0 would imply \(5^{j} + 7^{l} = 2004\) but my point was that it's not immediate that you then have no possible solution. For example, using what Prom says there are powers of 7 ending with a 9 and all powers of 5 end with a 5 so their sum could indeed end in a 4.

    Now it's indeed true that there's no integers solution to \(5^{j} + 7^{l} = 2004\) and you can easily brute force it by considering \(2004-5^{j}\) for 0<j<5 and considering \(7^{l}\) for 0<l<4. However without doing any further consideration in terms of modular arithmetic or listing the powers it's not immediate that m>0. I'm making the point because Fudge wasn't sure how Guest reached his conclusion and Guest specified the method, you just stated it without justification.
     
  22. Tach Banned Banned

    Messages:
    5,265
    Did you read the problem statement? Here it is again:

    m being 0 excludes k=0.
     
  23. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    My mistake. Sorry

    Please Register or Log in to view the hidden image!

     

Share This Page