What is the remainder when divide 2^100 by 100?

Another approach

\(\frac{2^{100}}{100} = \frac{2^{100}}{2^2*25} = \frac{2^{98}}{25}\)

We know that \(2^7 = 128 = 3 (mod 25)\)

\(\frac{2^{98}}{25} = \frac{(2^7)^{14}}{25} = \frac{3^{14}}{25}\)

This will not help us much, but \(3^3 = 27 = 2 (mod 25)\)

And we have:

\(\frac{(3^3)^4*3^2}{25} = \frac{2^4*3^2}{25} = \frac{144}{25} = -6 (mod 25)\)

Now we need to multiply by cancelled factor \(2^2\)

\(-6*4 (mod 25*4) = -24 (mod 100) = 76 (mod 100)\)

Our remainder is 76

Hi,
One approach that can be used in all such Qs is to find closest multiples taking power..
Example here itself
\(2^100= (2^9)^{11}*2=512^{11}*2\)...
Now 512 to some power will leave a remainder same as 12 to that power..
So the remainder will be same as \(12^{11}*2\)...
\(12^{11}*2=(10+2)^{11}*2\)
Now when you expand this all terms except two terms willbe div by 100..
\(2^{11}*10^0+2^{10}*10^1=2048+1024*10\)
Last two digits are 48+40=88..
Remainder=88*2=176
That is 76

Rule: when a Number is Divided by 100, the Last 2 Digits of the Numerator/Dividend will be the Remainder


To find the last 2 Digits of (2)^100:


(2)^10 = 1024



Now if we just look at the last 2 Digits when we take (2)^20th Power:

(2)^20 = [ (2)^10 ] ^2 = [ ..... 24 ] ^2 = .......576 ----- Last 2 Digits will be 76



Again, looking at the last 2 Digits when we take (2)^30th Power

(2)^30 = (2)^10 * (2)^20 = [......24] * [....76] = .......24 ----- Last 2 Digits will be 24



Again, looking at the last 2 Digits when we take (2)^40th Power

(2)^40 = (2)^20 * (2)^20 = [.....76] * [......76] = .....76 ----- LAST 2 Digits will be 76



this Pattern will continue such that:


I. [(2)^10] ^ODD = Last 2 Digits will be = 24

II. [(2)^10] ^EVEN = Last 2 Digits will be = 76


(2)^100 = [ (2)^10 ] ^10 = [(2)^10] ^EVEN ----- LAST 2 Digits will be 76

-D-

\(\frac{2^{100}}{100} = \frac{2^{100}}{4*25}\)

We’ll find a remainder for 4 and 25 separately and use a Chinese remainder theorem to find a number.

\(2^{100} = 0 (mod 4)\) so our \(N = 0 (mod 4)\)

For 25 we’ll use slightly different approach.

GCF of \(2^{100}\) and \(25\) is \(1\), they are co-prime and we can apply Euiler's theorem.

\(2^{20} = 1 (mod 25)\) ---> \(2^{100} = (2^{20})^5 = 1^5 = 1\)

\(N = 1 (mod 25)\)

Combining two equations we’ll get

\(25x + 1 = 4y\)

or \(25x + 1 = 0 (mod 4)\) Solving this linear congruence we’ll get \(x=3 (mod 4)\)

and our number \(N = 25*3+1 =76\)

Answer D.

Solution:

The remainder when a number is divided by 100 is the last two digits of the number. Also, recall that if a number raised to a power has a remainder of r when it is divided by 100, the last two digits of the number raised to the same power also have r as the remainder when divided by 100. For example, 123^2 = 15129 has a remainder of 29 when divided by 100, 23^2 = 529 also has a remainder of 29 when divided by 100. Now, let’s use the fact that 2^10 = 1024. So we have:

2^20 = (2^10)^2 will have the same remainder as 24^2 = 576 when they are divided by 100 and notice that the remainder is 76.

2^40 = (2^20)^2 will have the same remainder as 76^2 = 5776 when they are divided by 100 and notice that the remainder is 76.

2^80 = (2^40)^2 will have the same remainder as 76^2 = 5776 when they are divided by 100 and notice that the remainder is 76.

As you can see, we are trying to get to 2^100 by squaring repeatedly, starting from 2^10. However, if we square again, we will have 2^160, which exceeds 2^100, the number we need to get to. However, notice that 2^100 = 2^80 x 2^20; therefore, we can just multiply the remainders of 2^80 and 2^20 to get the remainder of 2^100 when it’s divided by 100. Since the remainders of 2^80 and 2^20 are both 76, and 76 x 76 = 5776, the remainder is 76 when 2^80 x 2^20 = 2^100 is divided by 100.

Answer: D

Bunuel can you please take this one?

I tried to use this method but got the wrong answer
https://gmatclub.com/forum/remainder-wh ... l#p2327183

Can anyone please explain me, why only last two digits were find, when the question was asked to find the remainder ?

Because each number can be written as a multiple of 100+last 2 digits.
Example - 765 =700+65, when you divide it by 100, 700 is divisible by 100 and 65 is the remainder.

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.