A community for students.
Here's the question you clicked on:
 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?
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

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Maybe 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}\)?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1there the same thing, how much modular arithmetic do you know

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0I only know how to find x^y mod (n) using the trick that express y in binary number first, then take mod.

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Why are you deleting your comment?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1oh your refering to the binary exponentiation algorithm

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0This one: http://openstudy.com/updates/51165c4de4b09e16c5c86007

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$91^{71}\equiv 91 \text{ mod 100}$$ is what you are trying to show

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Suppose the question is find the last two digits of \(91^{71}\). How would you start?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1Do you know what the mod operator does?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1if I were to write 91^71 in base 10

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1it would be $$91^{71}=a+b10+c10^2+d10^3...$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1now we can reduce that modulo 100, ok

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Ehh!!! So, finding the last two digits of n is the same as finding n mod 100?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1so $$91^{71}\text{ mod 100}=a+10b$$ Where a is are first digit and b are second digit

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0And finding the last n digits of m is the same as finding m mod (10^n)?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1Which you can compute using your exponentiation by squaring algorithm or using a variety of other techniques

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1though for small numbers like yours, I wouldn't use that technique

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0What technique would you use?

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Don't tell me calculator ~_~

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1well for $$91^{71}\text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1I would reduce the 91 modulo 100, so I get,

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$91^{71} \text{ mod 100} = (9)^{71} \text{ mod 100}= 9^{71} \text{ mod 100}$$

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0"reduce the 91 modulo 100"?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1Yes, I think maybe you should read up a little on modular arithmetic,

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$91\equiv 9 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$91^{71}\equiv (9)^{71}\text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1so now we just have to compute 9 to the 71st power modulo 100

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1so its just computing $$9^{71}\text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{6}\equiv 1 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1raising both sides to the 12th power, gives

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{72}\equiv 1 \text{ mod 100 }$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{72}\equiv 1 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1but wqe want $$9^{71} \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1we have $$9x\equiv 1 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1now 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.

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1But 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.

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0I'll tag you if I have questions. I need to work it out myself to see if I really understand it. Sleep well :)

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.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)???

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1nice catch, this changes how you would proceed

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Don't be so lazy... :(

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{10}\equiv 1 \text{ mod 100 }$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1Which you can get by exponentiation by squaring

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1nvm im being stupid the original problem was $$9^{71} \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1this is the same as $$3^{142} \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1ahh maybe you should use your algorithm, i am to lazy to figure this out

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0142 is a LARGE number!!!

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1use the fact $$9^{10}\equiv 1 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1so $$9^{70}\equiv 1 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{71}\equiv 9\text{ mod 100}$$

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.09^(40) ≡1 mod 100 since phi(100) is 40 o_o

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{71}\equiv 9 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{71}\equiv 91 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$91^{71}\equiv 91 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1the first two digits of $$91^{71}$$ are 1 and 9

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.09^(10) ≡1 mod 100 < How do you work this out?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^2\equiv 19 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^4\equiv 19^2 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^4\equiv 39 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^8 \equiv 39^2 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^8\equiv 21 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{10}\equiv 21*9^2 \text{ mod 100}$$

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1$$9^{10}\equiv 1 \text{ mod 100}$$

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Got 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?

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1I raised both sides to the 7th power

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Ok, I didn't notice that, sorry!!

Jack17
 2 years ago
Best ResponseYou've already chosen the best response.1If $$a\equiv b \text{ mod m}$$ and $$c\equiv d \text{ mod m}$$ then $$ac\equiv bd \text{ mod m}$$

RolyPoly
 2 years ago
Best ResponseYou've already chosen the best response.0Thanks!!! 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 :)
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.