Find the remainder when 1^39 + 2^39 + 3^39 ... 12^39 is divided by 39.

Question

Find the remainder when 1^{39} +2^{39} + 3^{39}...12^{39} is divided by 39. A) 0 B) 1 C) 3 D) 2 E) 12 The solution will be posted on Monday 13 Sept, 22:00 IST. Please post explanations along with your answer. Happy Weekend Questions Archive : https://gmatclub.com/forum/happy-weekend ... 00374.html

gurpreetsingh · Accepted Answer

The answer is A -0

Solution 2:  Using the property :  a^n + b^n  is always divisible by  a+b  if n is odd

1^{39} +2^{39} + 3^{39}..........12^{39}

=>  1^{39} +12^{39} + 2^{39} + 11^{39} +3^{39} + 10^{39} + ......6^{39} + 7^{39}  is divisible by

1+12 + 2+11 + 3+10 + 4+9 + 5+8 + 7+6 = 6*13 = 39*2

=> it is divisible by 13 and the remainder is 0.

In general,  a^n + b^n ........ z^n  is divisible by  a+b+c......z  if n is odd

arpanpatnaik · Answer

This can be a possible way... If we look at the problem from the perspective of remainder theorem, Remainder of the Expression /39 = Sum of Individual Remainders of 1^39/39 , 2^39/39, ....and so on Now since all the numbers starting from 1 to 12 are less than 39, the remainders will be the numbers themselves. So the sum being 1+2+3...12 = 78. Now since 78 > denominator, the remainder is 78/39 which is equals to 0! It takes lesser time than the binomial approach! Hope it helps!

shrouded1 · Answer

Great question !

Split the sequence into sets of two such that each pair sums to 13. So  1^{39}+12^{39},2^{39}+11^{39},...,6^{39}+7^{39}

Now consider any one pair of these numbers  a^{39}+b^{39}  where  a+b=13 .

We know by the binomial theorem that  (a+b)^{39} = \Sigma_{r=0}^{39}( C_r^{39} a^{39} b^{39-r}) 
Now each term of this expansion except the first and last which are  a^{39}  and  b^{39}  is divisible by  39  since it contains a  C_{r}^{39}  where  1<=r<=38 . So the remainder when divided by 39 for the whole expansion is just the remainder when  a^{39}+b^{39}  is divided by 39.

Hence when  a+b=13  then  (a^{39}+b^{39}) mod 39 = (a+b)^{39} mod 39 = 13^{39} mod 39

This then reduces the problem to  (6 * (13^{39} mod 39)) mod 39

Now note that  13^2 mod 39 = 169 mod 39 = 13 
Therefore  13^{39} mod 39 = 13

So the final answer is  6 * 13 mod 39 = 78 mod 39 = 0

All this effort to get an answer = 0 !!

sandeep800 · Answer

Hey why this weekend scheme?by the end of next year we will only get 52 questions...

if u have doc or pdf upload that one if u dont have any issues? or post a question daily!!!

gurpreetsingh · Answer

I do not even have 52 questions :lol:

. I would have been happy to hear your comments on this, if you had posted the solution. But you have disappointed me. Any way good luck. --------this thread is meant only for question related discussion , for anything else pls PM me-----------

saxenashobhit · Answer

Hey gurpreet. nice explanation with simple formula to remember. I was really scared by reading binomial theorem. That may still be the root but I can live with simple formula u gave (i could relate with it by a^3 + b^3 expansion)

nonameee · Answer

Can this problem be solved easier (e.g. 1^13 + 2^13 + ... 12^13 = (1+2+3+..+12)(1^12 + ...12^12) ?

I understood the solution provided by shrouded1 but it's rather complicated and takes considerable effort.

The solution by gurpreetsingh is not clear because I don't get how from the fact that a^n + b^n is always divisible by a+b if n is odd he got that it is divisible by 39.

aylesspres · Answer

Hi,

When I calculate this summing the units digit of each integer ie 1^39 U=1; 2^39 U=8 and so on giving (1, 8, 7, 4, 5, 6, 3, 2, 9, 0, 1 and 8) the sum is 54 which leaves a remainder of 15. Obviously wrong but not sure why?

Any help? Thanks

aylesspres · Answer

Hi,

When I calculate this summing the units digit of each integer ie 1^39 U=1; 2^39 U=8 and so on giving (1, 8, 7, 4, 5, 6, 3, 2, 9, 0, 1 and 8) the sum is 54 which leaves a remainder of 15. Obviously wrong but not sure why?

Any help? Thanks

cyberjadugar · Answer

Hi,

2^n  (n>1) when divided by any number x, such that x > 2, the remainder will always be 2
similarly,  1^(39)+2^(39)+...+12^(39)  when divided by 39 will give remainder 1+2+3+...+12
so, we only have to check whether 1+2+...+12 or  \frac{(12*13)}{2} or 78 is divisible by 39, and it is.

thus, the remainder is 0.

Regards,

sanjoo · Answer

Is it GMAT type question?

Bunuel · Answer

________________________________________

No, it's not.

Find the remainder when 1^39 + 2^39 + 3^39 ... 12^39 is divided by 39.

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

Find the remainder when 1^39 + 2^39 + 3^39 ... 12^39 is divided by 39.

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards