2 ms·
The trick is to do the modulus before the exponentiation. It gives the same result. n^4 % x = m == (n % x)^4 % x = m By way of demonstration: n = 18, x
by Jtsummers 6y ago
The trick is to do the modulus before the exponentiation. It gives the same result.
n^4 % x = m
== (n % x)^4 % x = m
By way of demonstration:
n = 18, x = 15
18^4 = 104976 = 6 (mod 15)
----
18 % 15 = 3
3^4 = 81 = 6 (mod 15)
A very handy result to remember for cases where you don't want to use or don't have easy access to arbitrary precision integers.
- anthk 6y agoWell, this doesn't need much of a demonstration. The rest of a division will be the same "visually" if you keep "stacking" the same number on top.