Сравнения первой степени

Определение 9.4. Пусть а, b — целые числа ит> 1 — натуральное число. Мы будем говорить, что числа, а и Ь сравнимы по модулю т и записывать а = b (modin), если т (а — Ь) или, что аналогично, а = b + кт для некоторого целого значения к.

Пусть целое число b удовлетворяет неравенствам 0 ^ b < га. Из определения 9.4 следует, что решениями сравнения.

являются все целые числа вида г = Ъ + кт, где к — некоторое целое число. Данные числа образуют класс чисел по модулю га.

Определение 9.5. Любое число из класса b+km, k eZ, мы будем называть вычетом по модулю т. Наименьшее положительное число из данного класса принято называть наименьшим неотрицательным вычетом по модулю числа га.

Будем считать, что вычеты z и z различны, если они принадлежат разным классам вычетов.

Возьмем из каждого класса по модулю га одного представителя — наименьший неотрицательный вычет. Легко видеть, что таких вычетов всего га штук и все они различны.

Определение 9.6. Мы будем называть полной системой вычетов множество всех наименьших неотрицательных вычетов по модулю га.

Далее, для простоты изложения мы будем называть вычетами числа, принадлежащие полной системе вычетов.

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

Определение 9.7. Пусть выполнено сравнение az = 1 (modrn). Мы будем говорить, что вычет z является обратным к вычету, а и записывать z = а^-1 (;modm).

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

Для поиска обратимых элементов в кольце Z_TO необходимо рассмотреть сравнение.

и искать вычеты, но модулю т, удовлетворяющие сравнению (9.4) при 6=1. Верна следующая теорема.

Теорема 9.3 (см. [3, гл. 2J). Пусть а, Ь — целые числа и т > 0 — натуральное число.

Тогда для числа решений N сравнения az = 6 {modrn) выполнены равенства:

• 1. N = 1, если НОД (а, т) = 1,
• 2. N — d, если НОД (а, т) — d и d,
• 3. N = 0, в противном случае.

Если выполнено условие НОД (а, т) = 1, то легко найти вычет z, удовлетворяющий сравнению (9.4). Для этого достаточно воспользоваться леммой Безу. Действительно, если целые числа х и у удовлетворяют равенству.

то выполнено ах — 1 — ту и ах = 1 (mod т). Тогда, определяя 2 сравнением z = xb (mod ш), получим.

Если же выполнено равенство НОД (а, т) = d для некоторого натурального d > 1, то определим числа а = и гщ = '-j. Применяя к этим числам лемму Безу, найдем целые числа х и у такие, что

Вычет г, удовлетворяющий (9.4), может быть определен сравнением.

для всех возможных значений к — 0,1,… , d — 1, где Ь = ^. Легко проверить, что.

Теперь, мы обобщим сравнение (9.4) и рассмотрим систему.

где п — некоторое натуральное число, а,…, а_п, Ь,…, Ъ_п — произвольные целые числа, a mi,…, т_п — взаимно простые в совокупности числа.

Используя способ нахождения решений сравнения (9.4), мы можем независимо свести каждое уравнение этой системы к системе, в которой в левой части сравнения вместо коэффициентов oi,…, a_n будут стоять единицы. Для нахождения решений полученной системы сравнений может быть использована следующая теорема, которую принято называть китайской теоремой об остатках.

Теорема 9.4 (см. [2]). Пусть п — натуральное число и ть …, т_п — целые, взаимно простые числа, произведение которых равно М — П;_{= L} nij. Тогда для любого набора целых чисел а, …, а_п решение системы сравнений

Сравнение (9.6) позволяет в явном виде записать вычет х, удовлетворяющий системе сравнений (9.5). Поскольку операция приведения по модулю М является достаточно трудоемкой, мы можем предложить другой алгоритм вычисления неизвестного вычета х, использующий вычисления с числами, не превосходящими п. Данный алгоритм вытекает из доказательства следующей теоремы.

Теорема 9.5 (Гарнер). Пусть т, …, т_п — целые взаимно простые числа, произведение которых равно М = П)=1 ^тг Пусть х < М — целое число, удовлетворяющее системе сравнений (95). Тогда найдутся такие целые х,…, х_п, что х, < т, для всех г = 1, …, п и

Тогда равенство (9.7) принимает вид х — i ^x^i? Определим две последовательности значений xi,… , х_п и si,…, s_n в соответствии с формулами.

для всех г = 2,…, п. Легко видеть, что величина х = s_n удовлетворяет равенству (9.7). Покажем, что она удовлетворяет и системе сравнений (9.5).

Из равенств (9.8) следует, что для любого г = 1 ,…, п выполнено.

Тогда соотношения (9.8) позволяют записать.

и х действительно удовлетворяет системе сравнений (9.5).

Пам осталось показать, что выполнено неравенство х < М. Для начала заметим, что в силу определения для коэффициентов х_г выполнены неравенства х; < пц для всех г = 1,… , п.

Далее докажем с использованием индукции, что выполнено неравенство Si < midi для любого индекса г = 1 Для.

si = x < mi неравенство очевидно. Далее, пусть оно выполнено для всех индексов, меньших г. Тогда s*_i < = d> и.

Применяя полученное неравенство к индексу г = гг, получаем, что х = Sk < тфк = М. Теорема доказана. ?

Явно выписанные нами в доказательстве теоремы соотношения (9.7) позволяют вычислить неизвестное х, удовлетворяющее системе сравнений (9.5), без вычислений по модулю большого числа М = mi***m_n. Для определения х необходимо вычислять обратные элементы по модулю маленьких чисел rai,…, ra_n. Такой способ вычисления был предложен в 1959 году американским математиком Харви Гарнером.