Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть

12.    Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.

13.    Если  и , то .

14.    Если , то множество общих делителей а и р совпадает с множеством общих делителей b и р. В частности,

15.    Если , , …, , то , где .

При делении целого числа на модуль р в остатке получается 0, 1, 2, 3,…, р – 1 чисел.

Отнесём все целые числа, дающие при делении на р один и тот же остаток в один класс, поэтому получится р – различных классов по модулю р.

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

Обозначим через А₀ – класс вычетов, которые при делении на р дают остаток 0.

Например, числа вида .

Через А₁ – числа, дающие при делении остаток 1.

Например, числа вида .

Через А₂ – числа, дающие при делении остаток 2.

Например, числа вида .

Через А_р-1 – числа, дающие при делении остаток р – 1.

Например, числа вида .

Полной системой вычетов по модулю р называется совокупность р-целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р. Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р: 0, 1, …, р – 1. Множество {0, 1, …, р – 1} называется полной системой наименьших неотрицательных вычетов по модулю р. Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р, есть полная система вычетов по модулю р. Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, …, р; полную систему наименьших по абсолютной величине вычетов:

 при чётном р и

 при р нечётном.

Можно ввести в рассмотрение приведённую систему вычетов по модулю р, т. е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.

Число классов, взаимно простых с модулем р, равно значению функции Эйлера φ(р).

  § 2. Теорема о делении с остатком. Алгоритм Евклида

Рассмотрим пример. Пусть р = 6.

Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

r = 0;

r = 1;

r = 2;

r = 3;

r = 4;

r = 5;

где через r обозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема: Разделить число на число , , с остатком, значит, найти пару целых чисел q и r, таких, что выполняются следующие условия: .

Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5, 6}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как ; фактор-множество  

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули . Чаще всего числа  выбирают из множества простых чисел.

Пусть …, .

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е.  где , то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел  можно выбрать остатки от деления числа А на р_i соответственно.

Рассмотрим гомоморфное отображение:

.

Тогда каждому целому числу А можно поставить в соответствие кортеж  наименьших неотрицательных вычетов по одному из соответствующих классов.

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

Для дальнейшего нам требуется расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа х и у, такие, что .

Действительно, пусть d – наименьшее целое положительное число вида , например, , где числа х₀ и у₀ не обязательно определены однозначно. Существование числа d следует только из принципа полной упорядоченности. Очевидно, что d > 0. Остаётся показать, что . Для этого надо проверить выполнение двух условий: а)  и ; б) если  и , то . Допустим, что свойство а) не выполняется и для определённости положим, что |. Тогда по теореме о делении с остатком , и, следовательно,

,

 что противоречит минимальности d. Выполнение свойства б) проверяется непосредственно:

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

 

 

 

 

  

 

 

В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения (а, b), не превосходит числа цифр в меньшем из чисел а и b, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.

Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством , где L(a) и L(b) – число цифр в а и b соответственно. В правом столбце этого алгоритма каждый остаток выражен через . Надо вычислить  и . Очевидно, что  и . Сравнивая обе части на i-м шаге, получим

откуда получается следующая индуктивная процедура вычисления  и

:   

 

Пример. Применим расширенный алгоритм Евклида к числам а = 342, b = 612. Весь алгоритм представим в виде следующей таблицы.

Расширенный алгоритм Евклида

Номер итерации	q	A0	a1	x0	x1	Y0	y1
0	-	342	612	1	0	0	1
1	0	612	342	0	1	1	0
2	1	342	270	1	-1	0	1
3	1	270	72	-1	2	1	-1
4	3	72	54	2	-7	-1	4
5	1	54	18	-7	9	4	-5
6	3	18	0	9	-34	-5	19

Заметим, что равенство  выполняется на каждом шаге итерации. Алгоритм выдаёт d = 18, x = 9, y = -5 и тогда 18=342∙9 + 612∙(-5).

  § 3. Китайская теорема об остатках и её роль в представлении чисел в СОК

Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках. Эта теорема формулируется следующим образом.

Теорема. Пусть  - попарно взаимно-простые числа, больше 1, и пусть . Тогда существует единственное неотрицательное решение по модулю Р следующей системы сравнений:

  …,  (3.1)

Другими словами, отображение, которое каждому целому числу х, , ставит в соответствие кортеж , где , , является биекцией кольца  на декартово произведение

 колец .

Существует много различных доказательств этой теоремы. Приведём конструктивное доказательство китайской теоремы об остатках.

Доказательство. Найдём число х, , удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа х вида  где q₁ – произвольное целое число. Для нахождения q₁ подставим значение х во второе сравнение системы, после чего получим  откуда  где  - обратный мультипликативный элемент к  по модулю . Такой элемент существует, так как  Найденное таким образом q₁ можно записать в виде

 

для некоторого целого числа . Подставив значение  в выражение

 

Теперь первые два сравнения могут быть заменены на одно

 (3.2)

Применим теперь описанную процедуру к сравнению (3.2) и к одному из оставшихся сравнений системы (3.1). Повторяя этот процесс k – 1 раз, мы в конечном итоге найдём число х, удовлетворяющее всем сравнениям системы (3.1).

Докажем единственность решения системы (3.1). Воспользуемся методом от противного. Предположим, что существует другое решение  системы (3.1). Тогда

для всех . Вычитая почленно из первого сравнения второе, получим истинное сравнение  откуда следует, что . Но тогда , следовательно, , так как . Этим завершается доказательство китайской теоремы об остатках.

Пример. Решим систему сравнений

 

Решение. Так как модули 13, 15, 19 попарно взаимно простые числа, то данная система имеет единственное решение по модулю . Сравнение  соответствует диофантовому уравнению , где . Заменяя х во втором сравнении системы на , получаем , т. е. . К числу 13 обратным мультипликативным элементом по модулю 15 является число 7. Умножая последнее сравнение на 7 и, переходя в нём к вычетам по модулю 15, получим . Таким образом, . Следовательно, , при этом все числа вида  являются решениями первых двух сравнений данной системы. Подставим в третье сравнение вместо х полученное выше значение  или . Так как (5, 19) = 1, то  или . Итак,

, то есть х = 274.

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

Вход: Пары ,  такие, что , , где каждое > 1 и (,) = 1 для  и  - короткие целые числа.

Выход: х – единственное наименьшее неотрицательное решение системы по модулю .

1.  Инициализация. Р:=1; х:=МОД(,) – подпрограмма нахождения остатка деления  на .

2.  Цикл для i от 1 до n – 1: MOДINV(p, );

q:=МОД(