A not so easy problem:
Find the remainder when \( 2^{400} \) is divided by \( 400 \)?

- anonymous

A not so easy problem:
Find the remainder when \( 2^{400} \) is divided by \( 400 \)?

- katieb

See more answers at brainly.com

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- LollyLau

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

- anonymous

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

- LollyLau

176. (may be wrong)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- LollyLau

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

- 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.

- anonymous

You can't divide the numbers like that :)

- asnaseer

?

- anonymous

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

- anonymous

work*

- 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?

- asnaseer

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

- anonymous

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

- asnaseer

So is my solution valid and correct?

- anonymous

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

- anonymous

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

- asnaseer

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

- anonymous

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

- asnaseer

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

- asnaseer

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

- 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.

- asnaseer

*The last digit pair

- anonymous

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

- anonymous

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

- asnaseer

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

- anonymous

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

Looking for something else?

Not the answer you are looking for? Search for more explanations.