Суть: остатки можно складывать, вычитать и умножать, т.е.:

(a+b) mod n =( (a mod n) + (b mod n) ) mod n

a*b mod n = ( (a mod n) * (b mod n) ) mod n

a$^b$ mod n = (a mod n)$^b$ mod n