Vedic method to find the last two digits of any number raised to some power
Answers
Answered by
0
AFAIK you’re just going to have to do the brute-force multiplication. The only shortcut I can offer is that the following should be true:
(x^y) mod k == [(x mod k) * (x mod k) * … (x * mod k)] mod k
The latter is an uglier and more complex form, but for k==100, or k==1000 it means that you can scrape the last couple digits off for the convenience of processing this either in your head or on paper.
Example:
x = 5, y = 7, let k = 1000
5^7 = (5 mod 1000) * (5 mod 1000) * … * (5 mod 1000)
Simplifies in your head to:
x = 5y = 1x = (x * 5) mod 1000y = y + 1if y =/= 7 then goto step 3
In practice:
x = 5x = 25x = 125x = 625x = 3125 mod 1000 = 125
[Yay, we get to throw away leading digits for convenience!]x = 125 * 5 mod 1000 = 625x = 625 * 5 mod 1000 = 3125 mod 1000 = 125
Just to confirm this, 5^7 is 78125, which if we take the last 3 digits is 125. So it checks out.
(x^y) mod k == [(x mod k) * (x mod k) * … (x * mod k)] mod k
The latter is an uglier and more complex form, but for k==100, or k==1000 it means that you can scrape the last couple digits off for the convenience of processing this either in your head or on paper.
Example:
x = 5, y = 7, let k = 1000
5^7 = (5 mod 1000) * (5 mod 1000) * … * (5 mod 1000)
Simplifies in your head to:
x = 5y = 1x = (x * 5) mod 1000y = y + 1if y =/= 7 then goto step 3
In practice:
x = 5x = 25x = 125x = 625x = 3125 mod 1000 = 125
[Yay, we get to throw away leading digits for convenience!]x = 125 * 5 mod 1000 = 625x = 625 * 5 mod 1000 = 3125 mod 1000 = 125
Just to confirm this, 5^7 is 78125, which if we take the last 3 digits is 125. So it checks out.
Similar questions