остатка по модулю pi не предопределяет вида остатка этого же числа по модулю р/. Если, например, /?, = 2, а /?2 = 4, то множество разбивается не на восемь остаточных классов, а лишь на четыре остаточных класса, соответствующих остаткам от деления чисел из Л/ на 4. Эти остатки предопределяют результат : деления на 2. Если остатки от деления на 4 равны О, 2, то остаток от деления на 2 равен 0. При остальных остатках от деления числа на 4 остаток от деления на 2 равен 1.

Каждому числу х и каждой системе модулей Р2, ... рд однозначно соответствует остаточный класс, к которому относится число X. в обратную сторону однозначности нет, ибо остаточные классы состоят из бесконечного множества элементов. L Выделим теперь в каждом классе элемент, минимальный по своему числовому значению. Этот элемент будем называть главным элементом (в теории чисел главный элемент обычно называется абсолютно наименьшим вычетом). Пусть М есть множество главных элементов для данной системы модулей. Если мы будем рассматривать только М, то для данной системы модулей и некоторого числа х, являющегося главным элементом, существует взаимно-однозначное соответствие между X и остаточным классом, к которому это X относится.

Вместо множества главных элементов можно брать любое множество М, элементы которого получаются из элемента М прибавлением к каж;ому из них числа k PiP2-P„{k=\, 2,...). Введем важное для нас в дальнейшем понятие формальной обратной величины по модулю pi для числа л:. По определению будем считать у обратной формальной «величиной для х, если выполнено сравнение ху\ (mod pj). Имеет место следующая теорема.

Теорема 6.5. (теорема Ферма). Для всякого числа X при простом модуле р имеет место сравнение х" х{тойр).

Доказательство. Рассмотрим случай, когда х взаимно просто с р. В теореме Ферма доказательство ведется при более общих предположениях, но нас в дальнейшем"будет интересовать лишь такой случай. Возьмем множество М, определяемое модулем р.

Обозначим элементы этого множества как л,, лга,..., Хр. Покажем, что множество ах,, ах,..., ах образует класс для данного модуля р. Для этого достаточно показать, что среди чисел вида ах нет ни одной пары, сравнимой по модулю р. Предположим противное. Пусть = алгу (mod/?) и i-fj. Но тогда,-используя теорему 6.3, мы получим, что имеет место сравнение лг; = JC,-(modp), что противоречит условию о принадлежности Xi и Xj к множеству М.

Таким образом, среди axi должны находится представители всех, остаточных классов и каждый из классов представляется одним числом.. Отсюда следует, что ах, ах, ... , ах образуют некоторое мно-„ жество М. Но тогда имеют место сравнения axi= bi (modр), ах2= b (modр), ..., aXp i= bp i (mod p). 3a числа 6,, - » p-i можно взять те же числа Xi, JCg, ...,. Xp i в соответствующем, (может быть, отличном от первоначального) порядке. Тогда

0x,=X;mod/?), « . ах2 = (mod р),

aXp i = Xij, i(modp).

На основании теоремы 6.1 произведем перемножение сравнений. Тогда получим

аР-х... Xj, i = л:,Х2... Xp i (mod/?).

Так как х,Х2... Xp iO(mod/?) (число х, соответствующее нулевому остатку, мы исключили из рассмотрения), то в последнем сравнении, перенося правую часть сравнения влево, мы получим

(а- - 1) Х1Х2... Хр 1 = О (mod/?).

В силу того что произведение Xi несравнимо с нулем, полученное сравнение эквивалентно сравнению - 1=0 (mod/?). Или «"= 1 (modр). Умножая обе части полученного сравнения на а, получим окончательно а- = а (mod /?).

Рассмотрим теперь сравнение ху = 1 (mod/?,). Из доказанной теоремы следует, что х"= 1 (mod/?,-). Следовательно, формальная Обратная величина для х по

модулю Pi есть л". В нижеследующей таблице приведены формальные обратные величины для некоторых чисел X и- некоторых модулей.

Таблица 6.1

Формальная обратная величина к х

В этой таблице приведены лишь наименьшие формальные обратные величины. Прочерки соответствуют случаям, когда число и модуль не являются взаимно простыми.

Введем теперь некоторый специальный способ кодирования числовой информации, использующий введенный нами аппарат теории сравнений.

В качестве номера класса (кода класса) возьмем

набор rest ~; rest rest - остатков, получаю-

Pi Р2 Рд

щихся от деления данного числа х (главного элемента) на модули данной системы. Определение 6.2. Если

элементом, то rest

rest

является

главным

rest

называется

Pi Ps

кодом в остатках числа х.

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

П Pi элементов: [О, 1,..., П А" 1} •

j=i 1=1 , ;