Конгруэнтные целые числа и модуль

Для решения вышеизложенного можно использовать простые тождества, важными из которых являются:

(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

и так далее и тому подобное. Поскольку это вопрос домашнего задания, я могу дать только подсказки, а не полное решение.

Вы также можете сделать это с помощью метода быстрого возведения в степень, где показатель степени выражается в степени двойки.