Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly

  • 2 years ago

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?

  • This Question is Closed
  1. RolyPoly
    • 2 years ago
    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}\)?

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

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

  3. RolyPoly
    • 2 years ago
    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.

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

    Why are you deleting your comment?

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

    oh your refering to the binary exponentiation algorithm

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

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

  7. Jack17
    • 2 years ago
    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

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

    Wait!

  9. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ok

  10. RolyPoly
    • 2 years ago
    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?

  11. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Do you know what the mod operator does?

  12. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    if I were to write 91^71 in base 10

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

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

  14. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    now we can reduce that modulo 100, ok

  15. RolyPoly
    • 2 years ago
    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?

  16. Jack17
    • 2 years ago
    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

  17. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yes pretty much

  18. RolyPoly
    • 2 years ago
    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)?

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

    yes

  20. Jack17
    • 2 years ago
    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

  21. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

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

    What technique would you use?

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

    Don't tell me calculator ~_~

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

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

  25. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  26. Jack17
    • 2 years ago
    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}$$

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

    "reduce the 91 modulo 100"?

  28. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  29. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    therefore

  31. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  32. Jack17
    • 2 years ago
    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

  33. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  34. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  35. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Now 9 is coprime to 100

  36. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  37. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  38. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    raising both sides to the 12th power, gives

  39. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  40. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  41. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  42. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  43. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  44. Jack17
    • 2 years ago
    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.

  45. Jack17
    • 2 years ago
    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.

  46. RolyPoly
    • 2 years ago
    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 :)

  47. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    alright later

  48. RolyPoly
    • 2 years ago
    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)???

  49. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    nice catch, this changes how you would proceed

  50. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    We want $$\phi(100)$$

  51. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    which is 40

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

    Don't be so lazy... :(

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

    Yay!!! Thanks!! :)

  54. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  55. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Which you can get by exponentiation by squaring

  56. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  57. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  58. Jack17
    • 2 years ago
    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

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

    142 is a LARGE number!!!

  60. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    then use your technique

  61. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  62. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  63. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

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

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

  65. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  66. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  67. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  68. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

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

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

  70. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  71. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  72. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  73. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  74. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  75. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  76. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  77. RolyPoly
    • 2 years ago
    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?

  78. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I raised both sides to the 7th power

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

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

  80. Jack17
    • 2 years ago
    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}$$

  81. RolyPoly
    • 2 years ago
    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 :)

  82. Jack17
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ye no problem

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