§ 8.5. Снова степени

Для систем сравнений, число уравнений в которых больше двух, есть свой вариант китайской теоремы об остатках. Мы ее сформулируем без доказательства, поскольку это просто еще одно приложение китайского алгоритма остатков. Снаг чала определение: натуральные числа называются попарно взаимно простыми, если для любой пары Например, три числа попарно взаимно простые, если

Китайская теорема об остатках. Пусть попарно взаимно простые натуральные числа. Тогда всякая система

имеет одно и только одно решение в

Применив эту версию теоремы, мы можем упростить вычисление вычетов степеней по модулю если известно его разложение на простые множители. Мы будем также предполагать, что каждый простой множитель входит в это разложение с кратностью 1, потому что именно в этом случае метод наиболее эффективен.

Допустим, что разложение имеет вид: где простые числа. Для целых мы сначала находим вычет по каждому модулю Бели простые множители не слишком велики, то вычисления будут очень быстрыми даже для больших поскольку нам помогает это делать теорема Ферма. Предположим, что мы уже сделали эти вычисления, причем

Поэтому для определения вычета по модулю нам нужно только решить систему сравнений:

Заметим, что модули системы — различные простые числа, поэтому они попарно взаимно просты. Значит, по китайской теореме об остатках, система всегда имеет решение, скажем, Более того, любые два таких решения сравнимы по модулю Так как тоже решение системы, имеем Следовательно, вычет по модулю

Приведем пример. Допустим, нам нужно найти вычет числа 26754 по модулю 1155. Раскладывая 1155 на множители,

найдем: Применив теорему Ферма к каждому из этих простых чисел, получим:

Таким образом, нам осталось решить систему:

с помощью китайского алгоритма остатков. По первому сравнению системы поэтому второе сравнение дает:

потому что тройка обратима по модулю 5 и на нее можно сократить обе части сравнения. Итак, Подставляя вместо х его выражение через в третье сравнение и решая его, получаем: Наконец, решая четвертое сравнение относительно мы имеем . Значит и 709 — искомый вычет числа 26754 по модулю 1155.