4.7 НЕЗАВИСИМЫЕ ОСТАТКИ

Одно из важнейших приложений теории сравнений — система счисления в остатках, в которой целое число х представлено набором его остатков (или вычетов) по взаимно простым модулям:

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

Рассмотрим, например, один из случаев системы счисления в остатках, когда имеется только два модуля —3 и 5:

Все упорядоченные пары различны, поскольку тогда и только тогда, когда

Согласно свойствам сравнений можно складывать, вычитать и умножать обе компоненты независимо. К примеру, если нужно умножить на по модулю 15, то вычисляются Ответом будет следовательно должно равняться 1. (Безусловно, так оно и есть.)

Сей принцип независимости полезен при вычислениях на компьютере в силу того, что разные компоненты можно обрабатывать раздельно (скажем, на разных компьютерах). Если в качестве каждого модуля тк выбраны различные простые числа ,

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

А в ряде случаев можно выполнять и деление. Предположим, например, что нужно вычислить точную величину некоторого большого определителя, составленного из целых чисел. Результатом будет некоторое целое число а границы для можно задать, исходя из размера его элементов. Однако все известные способы быстрого вычисления определителей требуют деления, а это приводит к дробям (и потере точности, если довольствоваться двоичными приближениями). Выход заключается в вычислении по ряду больших простых чисел — можно спокойно делить по модулю р, если только делитель не окажется кратным Это случается крайне редко, но если все-таки случается, то можно выбрать другое простое число. В конечном счете, знание для достаточно многих простых модулей позволяет установить величину

Но мы еще не объяснили, как от заданного набора остатков перейти к . Мы показали, что такой переход теоретически возможен, но сами вычисления могут оказаться столь внушительны, что практически сведут на нет всю эту затею. К счастью, имеется довольно несложный способ уладить дело, который можно проиллюстрировать на примере набора из нашей таблички. Ключевая идея состоит в разрешении данной проблемы для двух случаев (1,0) и (0,1); действительно, если то поскольку сравнения можно перемножать и складывать.

В нашем случае просмотр таблички дает как найти а и когда модули огромны? Иначе говоря, если то где тот путь, который приведет к числам а и удовлетворяющим каждому из уравнений

И опять на выручку приходит (4.5): с помощью алгоритма Евклида можно найти числа такие, что

Поэтому можно взять при необходимости приводя их по

При больших модулях для сведения вычислений к минимуму бывают необходимы и другие уловки; подробности выходят

за рамки этой книги, но их можно найти в книге [140, разд. 4.3]. Переход от остатков к соответствующим исходным числам — операция в принципе выполнимая, но достаточно медленная, так что выигрыша во времени выполнения можно достичь лишь при условии, что удается выполнить сразу некоторую последовательность операций в системе счисления в остатках перед обратным переходом.

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

если два решения такие, что считать одинаковыми?

В соответствии с установленными ранее общими правилами, вначале следует рассмотреть случай, когда та равно степени простого числа при Тогда сравнение может быть записано в виде

так что должно делить либо либо либо и то и другое. Но не может делить как так и если только не равно 2 (оставим этот случай напоследок). Если же то или поэтому имеется ровно два решения:

Случай несколько отличается. Если то одно из чисел или делится на 2 (но не на 4), а тогда другое число должно делиться на Это означает, что при к 3 имеется четыре решения, а именно, (Например, если то этими четырьмя решениями будут — полезно знать, что квадрат любого нечетного числа имеет вид )

Итак, тогда и только тогда, когда для всех простых чисел из канонического разложения на множители. Каждое простое число не зависит от других, и для (кроме случая имеется ровно две возможности. Поэтому если имеет ровно различных простых делителей, то общее число решений сравнения равно (за исключением поправки на четное . В общем случае точное число решений равно

Так, имеется четыре „квадратных корня из единицы по модулю а именно 1, 5, 7 и 11. При данная четверка — это числа, остатки которых по равны ±1, а именно (1,1), (1,4), (2,1) и (2,4) в системе счисления в остатках. В обычной (десятичной) системе счисления этими решениями будут 1, 4, 11 и 14.