Question

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?

Answer 1

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}\)?

Answer 2

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

Answer 3

I only know how to find x^y mod (n) using the trick that express y in binary number first, then take mod.

Answer 4

Why are you deleting your comment?

Answer 5

oh your refering to the binary exponentiation algorithm

Answer 6

This one:
http://openstudy.com/updates/51165c4de4b09e16c5c86007

Answer 7

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

Answer 8

Wait!

Answer 9

ok

Answer 10

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

Answer 11

Do you know what the mod operator does?

Answer 12

if I were to write 91^71 in base 10

Answer 13

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

Answer 14

now we can reduce that modulo 100, ok

Answer 15

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

Answer 16

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

Answer 17

yes pretty much

Answer 18

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

Answer 19

yes

Answer 20

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

Answer 21

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

Answer 22

What technique would you use?

Answer 23

Don't tell me calculator ~_~

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

"reduce the 91 modulo 100"?

Answer 28

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

Answer 29

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

Answer 30

therefore

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

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

Answer 35

Now 9 is coprime to 100

Answer 36

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

Answer 37

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

Answer 38

raising both sides to the 12th power, gives

Answer 39

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

Answer 40

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

Answer 41

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

Answer 42

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

Answer 43

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

Answer 44

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.

Answer 45

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.

Answer 46

I'll tag you if I have questions. I need to work it out myself to see if I really understand it. Sleep well :)

Answer 47

alright later

Answer 48

@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)???

Answer 49

nice catch, this changes how you would proceed

Answer 50

We want $$\phi(100)$$

Answer 51

which is 40

Answer 52

Don't be so lazy... :(

Answer 53

Yay!!! Thanks!! :)

Answer 54

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

Answer 55

Which you can get by exponentiation by squaring

Answer 56

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

Answer 57

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

Answer 58

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

Answer 59

142 is a LARGE number!!!

Answer 60

then use your technique

Answer 61

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

Answer 62

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

Answer 63

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

Answer 64

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

Answer 65

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

Answer 66

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

Answer 67

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

Answer 68

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

Answer 69

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

Answer 70

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

Answer 71

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

Answer 72

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

Answer 73

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

Answer 74

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

Answer 75

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

Answer 76

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

Answer 77

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?

Answer 78

I raised both sides to the 7th power

Answer 79

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

Answer 80

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

Answer 81

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 :)

Answer 82

ye no problem