RolyPoly
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?
Delete
Share
This Question is Closed
RolyPoly
Best Response
You've already chosen the best response.
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}\)?
Jack17
Best Response
You've already chosen the best response.
1
there the same thing, how much modular arithmetic do you know
RolyPoly
Best Response
You've already chosen the best response.
0
I only know how to find x^y mod (n) using the trick that express y in binary number first, then take mod.
RolyPoly
Best Response
You've already chosen the best response.
0
Why are you deleting your comment?
Jack17
Best Response
You've already chosen the best response.
1
oh your refering to the binary exponentiation algorithm
Jack17
Best Response
You've already chosen the best response.
1
$$91^{71}\equiv 91 \text{ mod 100}$$ is what you are trying to show
RolyPoly
Best Response
You've already chosen the best response.
0
Wait!
Jack17
Best Response
You've already chosen the best response.
1
ok
RolyPoly
Best Response
You've already chosen the best response.
0
Suppose the question is find the last two digits of \(91^{71}\). How would you start?
Jack17
Best Response
You've already chosen the best response.
1
Do you know what the mod operator does?
Jack17
Best Response
You've already chosen the best response.
1
if I were to write 91^71 in base 10
Jack17
Best Response
You've already chosen the best response.
1
it would be $$91^{71}=a+b10+c10^2+d10^3...$$
Jack17
Best Response
You've already chosen the best response.
1
now we can reduce that modulo 100, ok
RolyPoly
Best Response
You've already chosen the best response.
0
Ehh!!!
So, finding the last two digits of n is the same as finding n mod 100?
Jack17
Best Response
You've already chosen the best response.
1
so $$91^{71}\text{ mod 100}=a+10b$$ Where a is are first digit and b are second digit
Jack17
Best Response
You've already chosen the best response.
1
yes pretty much
RolyPoly
Best Response
You've already chosen the best response.
0
And finding the last n digits of m is the same as finding m mod (10^n)?
Jack17
Best Response
You've already chosen the best response.
1
yes
Jack17
Best Response
You've already chosen the best response.
1
Which you can compute using your exponentiation by squaring algorithm or using a variety of other techniques
Jack17
Best Response
You've already chosen the best response.
1
though for small numbers like yours, I wouldn't use that technique
RolyPoly
Best Response
You've already chosen the best response.
0
What technique would you use?
RolyPoly
Best Response
You've already chosen the best response.
0
Don't tell me calculator ~_~
Jack17
Best Response
You've already chosen the best response.
1
well for $$91^{71}\text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
I would reduce the 91 modulo 100, so I get,
Jack17
Best Response
You've already chosen the best response.
1
$$91^{71} \text{ mod 100} = (-9)^{71} \text{ mod 100}= -9^{71} \text{ mod 100}$$
RolyPoly
Best Response
You've already chosen the best response.
0
"reduce the 91 modulo 100"?
Jack17
Best Response
You've already chosen the best response.
1
Yes, I think maybe you should read up a little on modular arithmetic,
Jack17
Best Response
You've already chosen the best response.
1
$$91\equiv -9 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
therefore
Jack17
Best Response
You've already chosen the best response.
1
$$91^{71}\equiv (-9)^{71}\text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
so now we just have to compute -9 to the 71st power modulo 100
Jack17
Best Response
You've already chosen the best response.
1
but $$(-1)^{71}=-1$$
Jack17
Best Response
You've already chosen the best response.
1
so its just computing $$-9^{71}\text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
Now 9 is coprime to 100
Jack17
Best Response
You've already chosen the best response.
1
and $$\phi(9)=6$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^{6}\equiv 1 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
raising both sides to the 12th power, gives
Jack17
Best Response
You've already chosen the best response.
1
$$9^{72}\equiv 1 \text{ mod 100 }$$
Jack17
Best Response
You've already chosen the best response.
1
$$-9^{72}\equiv -1 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
but wqe want $$-9^{71} \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
if we let $$-9^{71}=x$$
Jack17
Best Response
You've already chosen the best response.
1
we have $$9x\equiv -1 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
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.
Jack17
Best Response
You've already chosen the best response.
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.
RolyPoly
Best Response
You've already chosen the best response.
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 :)
Jack17
Best Response
You've already chosen the best response.
1
alright later
RolyPoly
Best Response
You'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
Best Response
You've already chosen the best response.
1
nice catch, this changes how you would proceed
Jack17
Best Response
You've already chosen the best response.
1
We want $$\phi(100)$$
Jack17
Best Response
You've already chosen the best response.
1
which is 40
RolyPoly
Best Response
You've already chosen the best response.
0
Don't be so lazy... :(
RolyPoly
Best Response
You've already chosen the best response.
0
Yay!!! Thanks!! :)
Jack17
Best Response
You've already chosen the best response.
1
$$9^{10}\equiv 1 \text{ mod 100 }$$
Jack17
Best Response
You've already chosen the best response.
1
Which you can get by exponentiation by squaring
Jack17
Best Response
You've already chosen the best response.
1
nvm im being stupid the original problem was $$-9^{71} \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
this is the same as $$-3^{142} \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
ahh maybe you should use your algorithm, i am to lazy to figure this out
RolyPoly
Best Response
You've already chosen the best response.
0
142 is a LARGE number!!!
Jack17
Best Response
You've already chosen the best response.
1
then use your technique
Jack17
Best Response
You've already chosen the best response.
1
use the fact $$9^{10}\equiv 1 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
so $$9^{70}\equiv 1 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^{71}\equiv 9\text{ mod 100}$$
RolyPoly
Best Response
You've already chosen the best response.
0
9^(40) ≡1 mod 100
since phi(100) is 40 o_o
Jack17
Best Response
You've already chosen the best response.
1
$$-9^{71}\equiv -9 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$-9^{71}\equiv 91 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$91^{71}\equiv 91 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
the first two digits of $$91^{71}$$ are 1 and 9
RolyPoly
Best Response
You've already chosen the best response.
0
9^(10) ≡1 mod 100 <- How do you work this out?
Jack17
Best Response
You've already chosen the best response.
1
$$9^2\equiv -19 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^4\equiv 19^2 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^4\equiv -39 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^8 \equiv 39^2 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^8\equiv 21 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^{10}\equiv 21*9^2 \text{ mod 100}$$
Jack17
Best Response
You've already chosen the best response.
1
$$9^{10}\equiv 1 \text{ mod 100}$$
RolyPoly
Best Response
You've already chosen the best response.
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?
Jack17
Best Response
You've already chosen the best response.
1
I raised both sides to the 7th power
RolyPoly
Best Response
You've already chosen the best response.
0
Ok, I didn't notice that, sorry!!
Jack17
Best Response
You've already chosen the best response.
1
If $$a\equiv b \text{ mod m}$$ and $$c\equiv d \text{ mod m}$$ then $$ac\equiv bd \text{ mod m}$$
RolyPoly
Best Response
You've already chosen the best response.
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 :)
Jack17
Best Response
You've already chosen the best response.
1
ye no problem