Good Question from a gmat Math Quizz

samirpandeyit62 wrote:What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is divided by 58?
57
1
30
0
28

zero

gabriel wrote:

samirpandeyit62 wrote:What will be the remainder when 13^7 + 14^7 + 15^7 + 16^7 is divided by 58?
57
1
30
0
28

zero

Lets consider this example before we proceed to the actual problem
7 can be written as a sum of two numbers, lets say 2 and 5 in this case
So,
7/3 is also 2/3 + 5/3 , where
the remainder for 2/3 is 2
the remainder for 5/3 is 2
hence the combined remainder is 2+2 =4 which is the same if 7 is divided by 3.
(note if the combined remainder is bigger than the divisor then we further divide if by the divisor to get the actual remainder).

Similarly in the above case we can expect [58]^7/58
to be written as
(13^7)/58 + (14^7)/58 + (15^7)/58 + (16^7)/58
so its nothing but [58]^7 / 58 hence the remainder is 0.

yes the OA is 0. gmatrant I solved pretty much in the same way as u did.

I solved it on similar lines as gmatrant, but wasnt too convinced at the last step - the place where we expect (58^7)mod 58 to be written as (13^7+14^7+15^7+16^7)mod 58. Plugged in few values and found out it holds good for a general case.
Is there theorem/formula to do this consistently?

Guys so does this mean that 13^7+14^7+15^7+16^7 is nothing but (13+14+15+16)^7??

No. It doesNOT mean that 13^7+14^7+15^7+16^7=(58)^7

It simply means that (13+14+15+16) is a factor of 13^7+14^7+15^7+16^7.

13^7+14^7+15^7+16^7 can be written as (13+14+15+16)*(some more terms).

Note that this is true only for odd powers.

rprasanna

Thanks Gmatrant! This is a really new approach to solve this kind of Qs! This stands very helpful for me...