A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
A not so easy problem:
Find the remainder when \( 2^{400} \) is divided by \( 400 \)?
anonymous
 5 years ago
A not so easy problem: Find the remainder when \( 2^{400} \) is divided by \( 400 \)?

This Question is Closed

LollyLau
 5 years ago
Best ResponseYou've already chosen the best response.0theres a rule for finding remainders... lemme check.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Wow, is that so? Can you please enlighten me? :)

LollyLau
 5 years ago
Best ResponseYou've already chosen the best response.0the number cycles every 20 numbers. i tried to simplify the exponent but sadly that didn't work :p

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1I 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 + (3981)\%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
 5 years ago
Best ResponseYou've already chosen the best response.0You can't divide the numbers like that :)

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0"We can first simplify the problem by dividing numerator and denominator by 4 to get" This won't always for remainders.

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1surely it must work? if, after remultiplying 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
 5 years ago
Best ResponseYou've already chosen the best response.1maybe I don't understand number theory well enough to understand that?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Yes if you again do the mod then it should work.

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1So is my solution valid and correct?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0But there are some pretty fine lines here, and I am not sure if this in in general.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0What I know, we can't cancel unless the factors are coprime.

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1Sounds like time for another lesson for me. Do you know any good online resources for this topic in particular?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Hm, sorry I don't know any for this in particular :(

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1Ok  no problems  time to google then... :)

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1BTW: The digit pair I wrote in the list above should be 08 and NOT 16

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Wait, 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 coprime works should be evident from CRT.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Btw this problem is good example for using http://en.wikipedia.org/wiki/Chinese_remainder_theorem

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Break 400 as 25 and 16 and then apply CRT, note (25,16)=1; so it works :)

asnaseer
 5 years ago
Best ResponseYou've already chosen the best response.1OK  Let me go learn some chinese then... :) Thanks again

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0It's an awesome tool :) Good luck ansaseer :)
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.