Here's the question you clicked on:

## ParthKohli Group Title A common technique for finding modulo $$10$$ of any huge number in the form $$a^b$$? one year ago one year ago

• This Question is Closed
1. ParthKohli Group Title

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.

2. ParthKohli Group Title

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

3. ParthKohli Group Title

$$n$$ has to be a two-digit number. (I actually have to find the last two digits)

4. ParthKohli Group Title

Something with a pattern?

5. shubhamsrg Group Title

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.

6. terenzreignz Group Title

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

7. shubhamsrg Group Title

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

8. ParthKohli Group Title

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

9. terenzreignz Group Title

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

10. terenzreignz Group Title

then multiply 39 to it again.

11. terenzreignz Group Title

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

12. ParthKohli Group Title

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

13. shubhamsrg Group Title

Ohh, I see.

14. terenzreignz Group Title

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.

15. terenzreignz Group Title

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

16. ParthKohli Group Title

Nice... can you give me another example?

17. terenzreignz Group Title

How about 6^5000 = n (mod 215)

18. terenzreignz Group Title

(sneakily thinking of simple problems) :>

19. ParthKohli Group Title

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

20. ParthKohli Group Title

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

21. ParthKohli Group Title

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

22. terenzreignz Group Title

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

23. ParthKohli Group Title

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

24. ParthKohli Group Title

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

25. ParthKohli Group Title

What should I do here?

26. terenzreignz Group Title

Hang on...

27. terenzreignz Group Title

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

28. ParthKohli Group Title

Oh...

29. terenzreignz Group Title

Wait, typo -.-

30. ParthKohli Group Title

Yes, isn't that 1 (mod 215)

31. terenzreignz Group Title

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

32. terenzreignz Group Title

And work from there...

33. terenzreignz Group Title

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

34. ParthKohli Group Title

$6^{5000}= 6^{4998} \times 36 \equiv$

35. terenzreignz Group Title

$1 \times 36 (\mod 215 \ \ \ \ \ )$

36. ParthKohli Group Title

$\equiv 36 \pmod{215}$

37. ParthKohli Group Title

Argh, you type fast. =3

38. terenzreignz Group Title

Awesomeness

39. ParthKohli Group Title

Another n00bish question coming up. Thanks man.

40. terenzreignz Group Title

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

41. ParthKohli Group Title

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