Question

A not so easy problem:

Find the remainder when \( 2^{400} \) is divided by \( 400 \)?

Answer 1

theres a rule for finding remainders... lemme check.

Answer 2

Wow, is that so? Can you please enlighten me? :)

Answer 3

176. (may be wrong)

Answer 4

the number cycles every 20 numbers. i tried to simplify the exponent but sadly that didn't work :p

Answer 5

I don't know if this counts as a proof but here goes.
We can first simplify the problem by dividing numerator and denominator by 4 to get:\[\frac{2^{400}}{400}=\frac{2^{398}}{100}\]This implies we just need to find the last two digits of \(2^{398}\) and then multiply that by 4 to get the desired answer.
Now, listing the last two digits of successive multiples of two (starting from 2), we notice the following pattern:
02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04, 16,
^
pattern starts repeating from 04 (i.e. initial 02 is never encountered again)

So, after skipping the initial 02, we therefore have a repeating pattern after every 20 digit pairs. I therefore used this to calculate the position of the last two digits:\[1 + (398-1)\%20=1+17=18\]and the 18th digit pair in the sequence above is 44.

Therefore, the remainder must be \(4*44=176\) which agrees with @LollyLau.

Answer 6

You can't divide the numbers like that :)

Answer 7

?

Answer 8

"We can first simplify the problem by dividing numerator and denominator by 4 to get"

This won't always for remainders.

Answer 9

work*

Answer 10

surely it must work? if, after re-multiplying the new remainder you get a number larger than 400, then you would just need to mod it with 400 and that should still work shouldn't it?

Answer 11

maybe I don't understand number theory well enough to understand that?

Answer 12

Yes if you again do the mod then it should work.

Answer 13

So is my solution valid and correct?

Answer 14

But there are some pretty fine lines here, and I am not sure if this in in general.

Answer 15

What I know, we can't cancel unless the factors are coprime.

Answer 16

Sounds like time for another lesson for me. Do you know any good online resources for this topic in particular?

Answer 17

Hm, sorry I don't know any for this in particular :(

Answer 18

Ok - no problems - time to google then... :-)

Answer 19

BTW: The digit pair I wrote in the list above should be 08 and NOT 16

Answer 20

Wait, I am pretty sure that you can't cancel like that and then multiply, what you can do is break up into coprime factors and then do something like this, why co-prime works should be evident from CRT.

Answer 21

*The last digit pair

Answer 22

Btw this problem is good example for using http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Answer 23

Break 400 as 25 and 16 and then apply CRT, note (25,16)=1; so it works :)

Answer 24

OK - Let me go learn some chinese then... :-)
Thanks again

Answer 25

It's an awesome tool :) Good luck ansaseer :)