A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

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

  • This Question is Closed
  1. LollyLau
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. LollyLau
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    176. (may be wrong)

  4. LollyLau
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  5. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    You can't divide the numbers like that :)

  7. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ?

  8. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  9. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    work*

  10. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  12. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  13. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    So is my solution valid and correct?

  14. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  15. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  16. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  17. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  19. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  20. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    *The last digit pair

  22. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  24. asnaseer
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  25. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.