Модульная арифметика

Любому школьнику известно, что числа 37 и 23 не равны. Но, если в утверждение «числа 23 и 37 равны» добавить два слова и ещё одно число, то утверждение станет верным. Что же это за волшебные слова?

Сегодня речь пойдёт про сравнение чисел по модулю другого числа. Если мы говорим, что число a сравнимо с числом b по модулю числа c, то это значит, что у чисел a и b одинаковые остатки при делении на c. Ещё говорят, что числа a и b равны по модулю c.
Естественно, рассуждать об этом можно только в контексте целых чисел, иначе смысл определения теряется. Записывают сравнимость так:
a ≡ b (mod c).
Ещё можно понимать сравнение по модулю таким образом: если разность чисел a и b нацело делится на число c, то эти числа сравнимы (равны) по модулю с. То же самое символами:
(a-b) ⋮ с <=> a ≡ b (mod c).

То есть чтобы фраза «числа 23 и 37 равны» стала верной, надо добавить «по модулю 2». Также подойдут добавки «по модулю 7» и «по модулю 14».

Разберём, например, такое утверждение: 36 ≡ 91 (mod 11).
Здесь сказано, что числа 36 и 91 сравнимы по модулю 11, то есть имеют одинаковые остатки при делении на 11. Проверим: 36 = 11*3 + 3, а 91 = 11*8 + 3. Остатки совпали!
Кстати, оба эти числа сравнимы с 3 по модулю 11, то есть с тем самым остатком от деления на 11.

Ещё пример: верно, что 29 ≡ 13 (mod 8), то есть числа 29 и 13 равны по модулю 8, ведь (29-13)⋮8. Более того, 29 ≡ 13 ≡ 5 (mod 8), ведь 5 — это и есть остаток от деления каждого из этих чисел на 8.

Сравнения по модулю имеют свойства, которые очень похожи на свойства обычных операций. Вот некоторые из них:
1) Если известно, что два числа сравнимы по модулю третьего, то их натуральные степени также будут сравнимы. То есть если a ≡ b (mod c), то для любого натурального k верно, что aᵏ ≡ bᵏ (mod c).
2) Сравнения можно складывать/вычитать и перемножать друг с другом, но только в том случае, если они берутся по одному модулю — а вот сравнения по разным модулям нельзя соединять, это будет неверно.
То есть если a ≡ b (mod c), n ≡ m (mod c), то
a + n ≡ b + m (mod c),
a*n ≡ b*m (mod c).

Большинство стандартных операций со сравнениями очень просто и привычно проделывать из-за схожести с обычными вычислениями. Но одна из упомянутых операций обладает интересным свойством! Дело в том, что возвести число в степень по модулю несложно — надо просто возвести число в нужную степень и найти остаток от деления (или искать остаток от деления на каждом шаге, так делать обычно проще).
Но вот выполнить обратную операцию, то есть найти «корень» нужной степени, гораздо труднее. Мало того, что этот процесс часто сводится к длинному перебору — иногда случается, что нужного нам корня вообще не существует. Из-за этих сложностей, принцип взятия остатка числа по какому-то модулю используется в криптографии: например, алгоритм (или, как его еще называют, протокол) Диффи-Хеллмана построен именно на том факте, что зашифровать одно число при помощи другого легко, а вот чтобы расшифровать не зная «код», понадобится много времени.

А теперь задачи для вас! Решения, как всегда, ждём под скрытым текстом.
1) С чем сравнимо число 1000*1001*1002*1003 по модулю 999?
2) С чем сравнимо 4²⁰²³ по модулю 3?
В обоих случаях требуются наименьшие возможные ответы. Они должны быть меньше, чем то число, по чьему модулю мы работаем.