anonymous 5 years ago A not so easy problem: Find the remainder when $$2^{400}$$ is divided by $$400$$?

1. LollyLau

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

2. anonymous

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

3. LollyLau

176. (may be wrong)

4. LollyLau

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

5. asnaseer

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.

6. anonymous

You can't divide the numbers like that :)

7. asnaseer

?

8. anonymous

"We can first simplify the problem by dividing numerator and denominator by 4 to get" This won't always for remainders.

9. anonymous

work*

10. asnaseer

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?

11. asnaseer

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

12. anonymous

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

13. asnaseer

So is my solution valid and correct?

14. anonymous

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

15. anonymous

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

16. asnaseer

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

17. anonymous

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

18. asnaseer

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

19. asnaseer

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

20. anonymous

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.

21. asnaseer

*The last digit pair

22. anonymous

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

23. anonymous

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

24. asnaseer

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

25. anonymous

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