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!
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
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.
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.
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.
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.
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.
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.
SORRY the question also states that that j,k,l and m are DIFFERENT non-negative integers. This probably makes it easier...
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.