What is the remainder when 23^35 + 35^35 is divided by 17?

himanshu14 Thank you for pointing out the error. It's 33^35+35^35. Edited the question.

(33^35 + 35^35)/17 = 33^35 /17 + 35^35 /17 = (34-1)^35 /17 + (34+1)^35 /17 = (-1)^35 /17 + (1)^35 /17 = (1-1)/17 = 0.

Answer must be A in my view.

Posted from my mobile device

This doesn’t seem like a GMAT question but here’s an explanation avoiding the use of any theorems:

33^35 = (34 - 1)^35. If you know powers well, you might see after expanding this all terms will have a factor of 34 but one, (-1)^35 = -1. Since every other term is related to 34, when we divide by 17 we’re left with a remainder of (-1) or 16. In short, when we are finding the remainder when dividing by 17 we can treat 33^35 as 16^35 or (-1)^35.

Similarly, 35^35 mod 17 = 1^35 mod 17 = 1. Therefore the remainder is -1 + 1 = 0 and the answer is A.

Can anyone explain the solution in any other way?

Posted from my mobile device

The formula in second method helps to understand it better. Thanks a lot!

Posted from my mobile device

How does (34-1)^35 become [34^35 -1^35]
and (34+1)^35 become [34^35 +1^35] ?

Mathematically, that's not possible -it's an incorrect expansion. I actually picturized this in my mind to make my calculations easier because it is an binomial expression and after expansion, the equation would become 34 raised to something, which makes 34/17 divisible. I hope it's clear now.
P.S: I have removed that particular part to avoid much confusion.

Actually its a part of binomial expansion of (34+1)^35 similar to (a+b)^n , every term in that expansion is associated with the 34^ something except 1^35 , since 34^ terms are all divisible by 17 , the only term in the expansion left is 1^ terms

Posted from my mobile device

Yeah I get that but if it's written as a part of binomial expansion, then other elements of the expansion cannot be disregarded. I would not expect everyone to
know binomial expansion and this line would definitely give a wrong formula for expansion to most people.

This is a classic example of binomial expansion -

\((a+b)^n = nC0*a^0*b^n + nC1*a^1*b^{n-1} + .... + nC{n-1}*a^{n-1}*b^1 + nCn*a^n*b^0\)

Given addition can be divided into -

\((34 - 1)^{35} + (34 + 1)^{35}\)

Expanding first binomial -

\( (34 - 1)^{35} = 35C0*{34}^0*{-1}^{35} + 35C1*{34}^1*{-1}^{34} + .... + 35C34*{34}^{34}*{-1}^1 + 35C35*{34}^{35}*{-1}^0\)

Here except the first number which resolves to -1, rest of the numbers are multiples of 34 which means they are divisible by 17.
This summation is 1 less than a number divisible by 17, which means that adding one to this number would be divisible by 17, so the remainder of the existing number would be 17 - 1 = 16

\((34 - 1)^{35} = 17p + 16\) --- (1)

Expanding second binomial -

\( (34 + 1)^{35} = 35C0*{34}^0*{1}^{35} + 35C1*{34}^1*{1}^{34} + .... + 35C34*{34}^{34}*{1}^1 + 35C35*{34}^{35}*{1}^0\)

Here again we see the same case, except the first number which resolves to 1, rest of the numbers are multiples of 34 which means they are divisible by 17.
This summation is 1 more than a number divisible by 17, which means that subtracting one from this number would be divisible by 17, so the remainder of the existing number would be 1

\((34 + 1)^{35} = 17q + 1\) --- (2)

Adding (1) and (2)

\((34 - 1)^{35} + (34 + 1)^{35} = 17p + 16 + 17q + 1\)
\((34 - 1)^{35} + (34 + 1)^{35} = 17*(p + q) + 17\)

From this we can clearly say that this number is divisible by 17 with remainder 0.

Answer: A