Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this and **thousands** of other questions.

See more answers at brainly.com

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this and **thousands** of other questions

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

Why are you deleting your comment?

oh your refering to the binary exponentiation algorithm

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

Wait!

ok

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

Do you know what the mod operator does?

if I were to write 91^71 in base 10

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

now we can reduce that modulo 100, ok

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

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

yes pretty much

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

yes

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

What technique would you use?

Don't tell me calculator ~_~

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

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

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

"reduce the 91 modulo 100"?

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

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

therefore

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

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

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

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

Now 9 is coprime to 100

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

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

raising both sides to the 12th power, gives

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

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

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

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

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

alright later

nice catch, this changes how you would proceed

We want $$\phi(100)$$

which is 40

Don't be so lazy... :(

Yay!!! Thanks!! :)

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

Which you can get by exponentiation by squaring

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

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

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

142 is a LARGE number!!!

then use your technique

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I raised both sides to the 7th power

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

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

ye no problem