Question

What is the remainder when 5^2009 + 13^2009 is divided by 3?
I did it by common sense, the last value would always be 5 for 5^2009, and for 13, it changes from 3-9-7-1... So the 2008th value would be 3, therefore the next would be 9. when you add 5 and 9, you get 14, the units would be 4, so the remainder would have to be 1. But another possibility is that the tens place could have 24. And thats why i need another approach to this problem. Thank you

Answer 1

@amistre64 @phi @TuringTest
please help :)

Answer 2

Use binomial -
(6-1)^2009 + (12 + 1)^2009

Answer 3

That helps, but is there any other way to do it? something which can be done with basic knowledge of mathematics. Because even though i know how that is done, it is not in our curriculum and this is an aptitude test so i dont believe that this is the only approach. Thank you :)
Help me though :P

Answer 4

I think the part of binomial being used in this question will come under aptitude (remainder maybe)..still I'll look for an alternate solution..in time.. :)

Answer 5

Thanks a lot! :)
Yes i will try it with binomial theorem quick though! :)

Answer 6

hint :
a^n + b^n = (a+b) (a^(n-1) - a^(n-2)b + a^(n-3)b^2 - ... - ab^(n-2) + b^(n-1))
for a, b are odd numbers

Answer 7

(5^2009 + 13^2009) : 3
= (5+13) (bla bla bla) : 3
= 18 * (........) : 3
obvious, 18 divisible by 3

Answer 8

I did it :D
Its basically by mathematical induction
5^x/3 would always give 1 as remainder, so would 13^x/3.
so remainder is 2 :D

Answer 9

no, its remainder is 0

Answer 10

let's check it on wolfram :)
http://www.wolframalpha.com/input/?i=remainder+%285^2009+%2B+13^2009%29%2F3
click the link ^

Answer 11

But how is that possible, and are you absolutely sure about it? Cause i dont see how that is possible.

Answer 12

why not, 1000% surely :)

Answer 13

If you know, then can you enlighten me with the theory behind this answer?

Answer 14

i already gave explanation above. see my first coment, please

Answer 15

but it says (5^2009 + 13^2009) not (5+13)^2009 :/
if you take that out, you'll have some real algebraic pellet left to deal with.
I don't really understood how you simply took 13+5 out like that :/

Answer 16

i didnt say (5+13)^2009
i said, by using factoring a^n + b^n = (a+b) (a^(n-1) - a^(n-2)b + a^(n-3)b^2 - ... - ab^(n-2) + b^(n-1))

so,
(5^2009 + 13^2009) can be factored be :
(5 + 13) * (5^2008 - 5^2007 * 13 - 5^2006 * 13^2 - .... + 13^2008)
= 18 * (5^2008 - 5^2007 * 13 - 5^2006 * 13^2 - .... + 13^2008)

now what will do you get, if 18 * (5^2008 - 5^2007 * 13 - 5^2006 * 13^2 - .... + 13^2008) divided by 3 ??????

Answer 17

if you still confused, this is the simple problem :

whats the remainder if 18 * 2 divided by 3 ?

Answer 18

Yes i understood now! Thanks a ton dude! :)
You're awesome!! :)

Answer 19

you're welcome ;)

Answer 20

There is also another way i just got. 13^x/3 always gives remainder 1, but
5^x/3 gives 1 when its even, but 2 when its odd. In this case 2009 is odd, so total remainder is 3. which is divisible by 3, so its simply remainder = 0 :)
Thanks :)

Answer 21

yeah, that's nice too

Answer 22

That was a great method :)