Question

A common technique for finding modulo \(10\) of any huge number in the form \(a^b\)?

Answer 1

It seems that you have to go through a lot of manipulations... a lot for doing that. Although I was thinking of a technique they use to figure all that out.

Answer 2

OK, I'm gonna change the topic to something else:\[39^{39} \equiv n\pmod{100}\]

Answer 3

\(n\) has to be a two-digit number.

(I actually have to find the last two digits)

Answer 4

Something with a pattern?

Answer 5

39 = -61 mod100

=>39^38 = 61^38 mod100
=>39^39 = 39*61^38 mod100

SInce 61^n always ends in 1, that multiplied by 39, will give last digit as 9, hmm, leme see for the second last.

Answer 6

Better yet,
39^5 = -1 mod 100
Use that:
39^39 = (39^5)^7 * 39^4 = (-1)^7 * 39^4 mod 100

Answer 7

Seems legit.
But on paper, who's gonna go till 39^5 ! :O

Answer 8

Very nice, can you tell me *how* you came up with that solution? What do you initially think?

Answer 9

square 39, and then only take the last two digits...

Answer 10

then multiply 39 to it again.

Answer 11

and only take the last two digits, again...

Answer 12

Ahem, that was beautiful. But is there a common way to figure out these solutions?

Answer 13

Ohh, I see.

Answer 14

The way I think of things, and it's a common trend that the way I do it is highly inefficient (LOL)

But when faced with a problem

b^p = n (mod k)

I try to see if there's an exponent to which b can be raised so that it is 1 (or -1) mod k first.

Answer 15

That "last two digits" trick only works because you were conveniently working under mod 100... XD

Answer 16

Nice... can you give me another example?

Answer 17

How about
6^5000 = n (mod 215)

Answer 18

(sneakily thinking of simple problems) :>

Answer 19

Arhmegurd.\[\left(6^{5}\right)^{1000} \equiv (6^2)^{1000} \equiv n \pmod{215}\]

Answer 20

\[\left(6^5\right)^{400} \equiv (6^2)^{400} \equiv n\pmod{215}\]

Answer 21

\[\left(6^5\right)^{120} \equiv 6^{240} \equiv n \pmod{215}\]

Answer 22

I'm not following o.O
You may be using a method I'm not familiar with, though... if you are, do continue :)

Answer 23

\[\left(6^{5}\right)^{48} \equiv 6^{96} \equiv n \pmod{215}\]

Answer 24

Hmm... I am just using \(6^2 \equiv 6^5 \pmod{215}\)

Answer 25

What should I do here?

Answer 26

Hang on...

Answer 27

I was rather hoping you'd go for
\[6^3 = 216 = -1(mod \ 215)\]

Answer 28

Oh...

Answer 29

Wait, typo
-.-

Answer 30

Yes, isn't that 1 (mod 215)

Answer 31

\[\large 6^3 = 216 = 1(\mod \ 215 \ \ \ \ )\]
Much better

Answer 32

And work from there...

Answer 33

\[\large 6^{5000} = 6^{3(1666)+2}\]

Answer 34

\[6^{5000}= 6^{4998} \times 36 \equiv \]

Answer 35

\[1 \times 36 (\mod 215 \ \ \ \ \ )\]

Answer 36

\[\equiv 36 \pmod{215}\]

Answer 37

Argh, you type fast. =3

Answer 38

Awesomeness

Answer 39

Another n00bish question coming up. Thanks man.

Answer 40

If you have time, look up Fermat's Little Theorem, might come in handy in a pinch.

Answer 41

Yesh, that one is cool:\[p^{n - 1} \equiv 1 \pmod{n} \]I'd try to see if that applies in the future.