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?

- anonymous

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- 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

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

- 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

Why are you deleting your comment?

- 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

Wait!

- anonymous

ok

- anonymous

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

- anonymous

Do you know what the mod operator does?

- anonymous

if I were to write 91^71 in base 10

- anonymous

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

- anonymous

now we can reduce that modulo 100, ok

- anonymous

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

- anonymous

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

- anonymous

yes pretty much

- anonymous

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

- anonymous

yes

- anonymous

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

- anonymous

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

- anonymous

What technique would you use?

- anonymous

Don't tell me calculator ~_~

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

"reduce the 91 modulo 100"?

- anonymous

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

- anonymous

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

- anonymous

therefore

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

Now 9 is coprime to 100

- anonymous

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

- anonymous

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

- anonymous

raising both sides to the 12th power, gives

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- 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

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

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

alright later

- 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

nice catch, this changes how you would proceed

- anonymous

We want $$\phi(100)$$

- anonymous

which is 40

- anonymous

Don't be so lazy... :(

- anonymous

Yay!!! Thanks!! :)

- anonymous

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

- anonymous

Which you can get by exponentiation by squaring

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

142 is a LARGE number!!!

- anonymous

then use your technique

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- anonymous

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

- 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

I raised both sides to the 7th power

- anonymous

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

- anonymous

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

- 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

ye no problem

Looking for something else?

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