Простые тождества могут быть использованы для решения вышеупомянутого, важными из которых являются:
(a + b) mod c = a mod c + b mod c
Кроме того,
ab mod c = (a mod c)*(b mod c)
Это может быть использовано для решения очень больших показателей, например, если вы хотите решить:
24^3100 mod 19
Вы могли бы, вероятно, разбить это как:
24^(310*100) mod 19
, который в дальнейшем можно записать как:
24^310 mod 19 x 24^100 mod 19
Вы можете далее разбить его на значения, которые вы могли бы фактически вычислить и решить. Например, если вы продолжите разбивать 100, вы можете решить
(24^4 mod 19)^25
и так далее, и тому подобное. Поскольку это домашнее задание, я могу дать только подсказки, а не полное решение.
Вы также можете сделать это с помощью метода быстрого возведения в степень, где показатель степени выражается в виде двух степеней.