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

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 !!

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!!!

I do not even have 52 questions .

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-----------

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)

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.

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

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

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,

Is it GMAT type question?

________________________________________

No, it's not.