anonymous
  • anonymous
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?
Discrete Math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
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}\)?
anonymous
  • anonymous
there the same thing, how much modular arithmetic do you know
anonymous
  • anonymous
I only know how to find x^y mod (n) using the trick that express y in binary number first, then take mod.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

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

Looking for something else?

Not the answer you are looking for? Search for more explanations.