# Tricky?

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

1. ### Fudge MuffinFudge MuffinRegistered 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?

Last edited: Jan 21, 2012

Messages:
5,265

5. ### RJBeeryNatural PhilosopherValued 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

7. ### Fudge MuffinFudge MuffinRegistered Senior Member

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

8. ### TachBannedBanned

Messages:
5,265
That m can only be {1,2,3}

9. ### Neddy BateValued 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 MuffinFudge MuffinRegistered Senior Member

Messages:
148
Is there any other way rather than trying all the possibilities until i get 2006?

11. ### prometheusviva 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. ### Guest254Valued 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.

Messages:
10,167
Nice

14. ### Fudge MuffinFudge MuffinRegistered Senior Member

Messages:
148
aw... brilliant.

But I don't follow lol, why must k be 0?

15. ### CptBorkRobbing the Shalebridge CradleValued Senior Member

Messages:
5,862
No it ain't. $5\equiv 5\quad (\mathrm{mod}\ 2006)$.

16. ### AlphaNumericFully ionizedRegistered 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. ### TachBannedBanned

Messages:
5,265
m cannot be 0 because k is already 0

18. ### AlphaNumericFully ionizedRegistered 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. ### TachBannedBanned

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 MuffinFudge MuffinRegistered 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. ### AlphaNumericFully ionizedRegistered 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. ### TachBannedBanned

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

m being 0 excludes k=0.

23. ### AlphaNumericFully ionizedRegistered Senior Member

Messages:
6,699
My mistake. Sorry