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

1. RolyPoly Group Title

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 Group Title

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

3. RolyPoly Group Title

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 Group Title

Why are you deleting your comment?

5. Jack17 Group Title

oh your refering to the binary exponentiation algorithm

6. RolyPoly Group Title
7. Jack17 Group Title

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

8. RolyPoly Group Title

Wait!

9. Jack17 Group Title

ok

10. RolyPoly Group Title

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

11. Jack17 Group Title

Do you know what the mod operator does?

12. Jack17 Group Title

if I were to write 91^71 in base 10

13. Jack17 Group Title

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

14. Jack17 Group Title

now we can reduce that modulo 100, ok

15. RolyPoly Group Title

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

16. Jack17 Group Title

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

17. Jack17 Group Title

yes pretty much

18. RolyPoly Group Title

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

19. Jack17 Group Title

yes

20. Jack17 Group Title

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

21. Jack17 Group Title

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

22. RolyPoly Group Title

What technique would you use?

23. RolyPoly Group Title

Don't tell me calculator ~_~

24. Jack17 Group Title

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

25. Jack17 Group Title

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

26. Jack17 Group Title

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

27. RolyPoly Group Title

"reduce the 91 modulo 100"?

28. Jack17 Group Title

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

29. Jack17 Group Title

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

30. Jack17 Group Title

therefore

31. Jack17 Group Title

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

32. Jack17 Group Title

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

33. Jack17 Group Title

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

34. Jack17 Group Title

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

35. Jack17 Group Title

Now 9 is coprime to 100

36. Jack17 Group Title

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

37. Jack17 Group Title

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

38. Jack17 Group Title

raising both sides to the 12th power, gives

39. Jack17 Group Title

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

40. Jack17 Group Title

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

41. Jack17 Group Title

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

42. Jack17 Group Title

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

43. Jack17 Group Title

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

44. Jack17 Group Title

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 Group Title

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 Group Title

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 Group Title

alright later

48. RolyPoly Group Title

@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 Group Title

nice catch, this changes how you would proceed

50. Jack17 Group Title

We want $$\phi(100)$$

51. Jack17 Group Title

which is 40

52. RolyPoly Group Title

Don't be so lazy... :(

53. RolyPoly Group Title

Yay!!! Thanks!! :)

54. Jack17 Group Title

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

55. Jack17 Group Title

Which you can get by exponentiation by squaring

56. Jack17 Group Title

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

57. Jack17 Group Title

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

58. Jack17 Group Title

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

59. RolyPoly Group Title

142 is a LARGE number!!!

60. Jack17 Group Title

61. Jack17 Group Title

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

62. Jack17 Group Title

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

63. Jack17 Group Title

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

64. RolyPoly Group Title

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

65. Jack17 Group Title

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

66. Jack17 Group Title

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

67. Jack17 Group Title

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

68. Jack17 Group Title

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

69. RolyPoly Group Title

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

70. Jack17 Group Title

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

71. Jack17 Group Title

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

72. Jack17 Group Title

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

73. Jack17 Group Title

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

74. Jack17 Group Title

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

75. Jack17 Group Title

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

76. Jack17 Group Title

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

77. RolyPoly Group Title

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 Group Title

I raised both sides to the 7th power

79. RolyPoly Group Title

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

80. Jack17 Group Title

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

81. RolyPoly Group Title

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 Group Title

ye no problem