Remainder Question

[apoorva.srivastva]

What is the remainder when 101^101 is divided by 25?

I dont have the OA

Please suggest a quick way to slove this on Test day!!!

[abhinav85]

OA Has to be 1.

just to solve it we can take it as 100^100
in this case the remainder is 0.

and if you solve 101^101,
the remainder will be 1.

[raleigh]

I'm not sure how you make the translation from 100^100 to 101^101 so quickly. The relationship is not obvious. Please give a detailed solution.

The key is that 101 ends with 1. 101^x will have the unit term ending in 1 since 1*1 = 1 and this is part of multiplying 101*101^y.

So your choices are 1, 11, and 21. The second term being 0 will force the tens digit to be 0 which will rule out 11 and 21 since the remainder has to be less than the divisor(25).

Do a few calculations and you should get a good feeling for this trend.

This seems like a problem you could sink a lot of time into. I'd like to know what the answer choices were. This seems like the type of problem that you do some initial investigation and eliminate some options. Maybe try another idea to see if you can solve it, otherwise guess.

I'd like to see a concise, quick solution to this. This post is just my quick approach to this problem. Good problem.

[Stuart@KaplanGMAT]

So your choices are 1, 11, and 21. The second term being 0 will force the tens digit to be 0 which will rule out 11 and 21 since the remainder has to be less than the divisor(25).

Doesn't 31/25 have a remainder of 6? When you divide a number ending in 1 by 25, the possible remainders are actually:

1, 6, 11, 16 and 25

While it's going to take forever and a day to actually calcluate the value of 101^101, if we do the first couple we can quickly see a pattern:

101*101 = 10101
10101*101 = 1010101

As the series progresses, we're just adding a "10" to the front of the expression.

When we divide by 25, all that matters is the last two digits (since 100 is divisible by 25). Once we recognize that 101^101 ends in "01", we know with certainty that the remainder is 1.

We also could have come to this conclusion by thinking in terms of quadratics:

101^2 = (100 + 1)^2 = 100^2 + 2(100*1) + 1 = 10000 + 100 + 1 = 10101

10101*101 = (10101)(100) + (10101)(1) = 1010100 + 1 = 1010101

and again, we can see the pattern that's developing.

[apoorva.srivastva]

Hii Stuart and Raleigh!!

thanks a ton for your inputs...

yeahh......u are right!!!

this question will be better solved by using the pattern!!!

also please tell me as to how can we apply the formula given below to good effect in this problem

When (a+1)^n/a then the remander is 1
irrespective of the fact that n is odd or even

Kindly help

[nadib002]

When (a+1)^n/a then the remander is 1
irrespective of the fact that n is odd or even

(101 ^ 101)/25

101 = 25*4 + 1

(101^101)25 =( (25*4 + 1)^101)/25 , which is in the form of( (a*k + 1) ^n)/a --> remainder is 1.

[kstv]

101*101 = 10101
I think Stuart meant 101²=10201 not 10101.
cos he wrote 101^2 = (100 + 1)^2 = 100^2 + 2(100*1) + 1

similarly 10101*101 = 1010101 = 1020201