Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly Group Title

Why is the last two digits of \(91^{71}\) the same as 91mod100? Similarly, why is it true that the last two digits of \(81^{81}\) the same as 81mod100, and that of \(71^{91}\) the same as 71mod100?

  • one year ago
  • one year ago

  • This Question is Closed
  1. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Maybe I should edit my question a bit. It should be "how do I know if the last two digits of \(91^{71}\) is the same as 91mod100? What if I need to find last two digits of\(91^{70}\)?

    • one year ago
  2. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    there the same thing, how much modular arithmetic do you know

    • one year ago
  3. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I only know how to find x^y mod (n) using the trick that express y in binary number first, then take mod.

    • one year ago
  4. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Why are you deleting your comment?

    • one year ago
  5. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oh your refering to the binary exponentiation algorithm

    • one year ago
  6. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    This one: http://openstudy.com/updates/51165c4de4b09e16c5c86007

    • one year ago
  7. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$91^{71}\equiv 91 \text{ mod 100}$$ is what you are trying to show

    • one year ago
  8. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Wait!

    • one year ago
  9. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ok

    • one year ago
  10. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Suppose the question is find the last two digits of \(91^{71}\). How would you start?

    • one year ago
  11. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Do you know what the mod operator does?

    • one year ago
  12. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    if I were to write 91^71 in base 10

    • one year ago
  13. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    it would be $$91^{71}=a+b10+c10^2+d10^3...$$

    • one year ago
  14. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    now we can reduce that modulo 100, ok

    • one year ago
  15. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ehh!!! So, finding the last two digits of n is the same as finding n mod 100?

    • one year ago
  16. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so $$91^{71}\text{ mod 100}=a+10b$$ Where a is are first digit and b are second digit

    • one year ago
  17. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yes pretty much

    • one year ago
  18. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    And finding the last n digits of m is the same as finding m mod (10^n)?

    • one year ago
  19. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yes

    • one year ago
  20. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Which you can compute using your exponentiation by squaring algorithm or using a variety of other techniques

    • one year ago
  21. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    though for small numbers like yours, I wouldn't use that technique

    • one year ago
  22. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    What technique would you use?

    • one year ago
  23. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Don't tell me calculator ~_~

    • one year ago
  24. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    well for $$91^{71}\text{ mod 100}$$

    • one year ago
  25. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I would reduce the 91 modulo 100, so I get,

    • one year ago
  26. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$91^{71} \text{ mod 100} = (-9)^{71} \text{ mod 100}= -9^{71} \text{ mod 100}$$

    • one year ago
  27. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    "reduce the 91 modulo 100"?

    • one year ago
  28. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, I think maybe you should read up a little on modular arithmetic,

    • one year ago
  29. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$91\equiv -9 \text{ mod 100}$$

    • one year ago
  30. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    therefore

    • one year ago
  31. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$91^{71}\equiv (-9)^{71}\text{ mod 100}$$

    • one year ago
  32. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so now we just have to compute -9 to the 71st power modulo 100

    • one year ago
  33. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but $$(-1)^{71}=-1$$

    • one year ago
  34. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so its just computing $$-9^{71}\text{ mod 100}$$

    • one year ago
  35. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Now 9 is coprime to 100

    • one year ago
  36. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    and $$\phi(9)=6$$

    • one year ago
  37. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{6}\equiv 1 \text{ mod 100}$$

    • one year ago
  38. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    raising both sides to the 12th power, gives

    • one year ago
  39. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{72}\equiv 1 \text{ mod 100 }$$

    • one year ago
  40. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$-9^{72}\equiv -1 \text{ mod 100}$$

    • one year ago
  41. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but wqe want $$-9^{71} \text{ mod 100}$$

    • one year ago
  42. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    if we let $$-9^{71}=x$$

    • one year ago
  43. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    we have $$9x\equiv -1 \text{ mod 100}$$

    • one year ago
  44. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    now all we have to do is solve for x modulo 100, and we have are solution, I know this looked like it took a while but its because I had to type over this chat, also there is many ways to solve somthing like this, if your just using a computer an algorithm like yours might be better.

    • one year ago
  45. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    But if your doing it by hand, its helpful to be familear with some of this stuff, because sometimes there are 'easyier' ways to do things.

    • one year ago
  46. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'll tag you if I have questions. I need to work it out myself to see if I really understand it. Sleep well :)

    • one year ago
  47. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    alright later

    • one year ago
  48. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @Jack17 Problem problem problem "Now 9 is coprime to 100" "and ϕ(9)=6" " \(9^6≡1 mod 100\)" But isn't it \(a^{\phi(n)} ≡ 1 (\mod n)\) ? Why would we find ϕ(9)???

    • one year ago
  49. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    nice catch, this changes how you would proceed

    • one year ago
  50. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    We want $$\phi(100)$$

    • one year ago
  51. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    which is 40

    • one year ago
  52. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Don't be so lazy... :(

    • one year ago
  53. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yay!!! Thanks!! :)

    • one year ago
  54. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{10}\equiv 1 \text{ mod 100 }$$

    • one year ago
  55. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Which you can get by exponentiation by squaring

    • one year ago
  56. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    nvm im being stupid the original problem was $$-9^{71} \text{ mod 100}$$

    • one year ago
  57. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    this is the same as $$-3^{142} \text{ mod 100}$$

    • one year ago
  58. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ahh maybe you should use your algorithm, i am to lazy to figure this out

    • one year ago
  59. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    142 is a LARGE number!!!

    • one year ago
  60. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    then use your technique

    • one year ago
  61. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    use the fact $$9^{10}\equiv 1 \text{ mod 100}$$

    • one year ago
  62. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so $$9^{70}\equiv 1 \text{ mod 100}$$

    • one year ago
  63. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{71}\equiv 9\text{ mod 100}$$

    • one year ago
  64. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    9^(40) ≡1 mod 100 since phi(100) is 40 o_o

    • one year ago
  65. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$-9^{71}\equiv -9 \text{ mod 100}$$

    • one year ago
  66. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$-9^{71}\equiv 91 \text{ mod 100}$$

    • one year ago
  67. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$91^{71}\equiv 91 \text{ mod 100}$$

    • one year ago
  68. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the first two digits of $$91^{71}$$ are 1 and 9

    • one year ago
  69. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    9^(10) ≡1 mod 100 <- How do you work this out?

    • one year ago
  70. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^2\equiv -19 \text{ mod 100}$$

    • one year ago
  71. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^4\equiv 19^2 \text{ mod 100}$$

    • one year ago
  72. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^4\equiv -39 \text{ mod 100}$$

    • one year ago
  73. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^8 \equiv 39^2 \text{ mod 100}$$

    • one year ago
  74. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^8\equiv 21 \text{ mod 100}$$

    • one year ago
  75. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{10}\equiv 21*9^2 \text{ mod 100}$$

    • one year ago
  76. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    $$9^{10}\equiv 1 \text{ mod 100}$$

    • one year ago
  77. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Got it! Have never thought that it works in this way... Another problem is that how you can draw the conclusion "so \( 9^{70}≡1 \mod 100\)" from \(9^{10}≡1 \mod 100\) quickly?

    • one year ago
  78. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I raised both sides to the 7th power

    • one year ago
  79. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok, I didn't notice that, sorry!!

    • one year ago
  80. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    If $$a\equiv b \text{ mod m}$$ and $$c\equiv d \text{ mod m}$$ then $$ac\equiv bd \text{ mod m}$$

    • one year ago
  81. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks!!! It looks pretty good now :) Btw, if you want to type LaTeX in the same line as the words, use \( instead of \[ . Thanks again for your help :)

    • one year ago
  82. Jack17 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ye no problem

    • one year ago
    • Attachments:

See more questions >>>

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.