Сравнения с одним неизвестным
Числа, равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа.
Соответственно m различным значениям r имеем m классов чисел по модулю m.
Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом.
Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Чаще всего в качестве полной системы вычетов употребляют наменьшие неотрицательные вычеты 0, 1, ..., m – 1.
Теорема 1. Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Доказательство. Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, так как их m, т. е. столько же сколько и классов, то в каждый класс наверно попадет по одному числу.
Теорема 2. Если D(a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b – любое целое, тоже пробегает полную систему вычетов по модулю m.
Доказательство. Действительно, чисел ax + b будет столько же сколько и чисел x, т. е. m. Согласно предыдущей теореме остается, следовательно, только показать, что любые два числа ax1 + b и ax2 + b отвечающие несравнимым x1 и x2, будут сами несравнимы по модулю m. Но допустив, что ax1 + b º ax2 + b (mod m), мы придем к сравнению ax1 º ax2 (mod m), откуда, вследствие D(a, m) = 1, получим x1 º x2 (mod m), что противоречит предположению о несравнимости чисел x1 и x2.
Рассмотрим сравнение такого общего вида:
f (x) º 0 (mod m); f(x) = axn + a1xn–1 +...+ an. (1)
Если a не делится на m, то n называется степенью сравнения. Решить сравнение – значит найти все значения x, ему удовлетворяющие. Два сравнения, которым удовлетворяют одни и те же значения x, называются равносильными.
Если сравнению (1) удовлетворяет какое-либо x = x1, то (следствие из теоремы, касающейся свойств сравнений) тому же сравнению будут удовлетворять и все числа, сравнимые с x1 по модулю m: x º x1 (mod m). Весь этот класс чисел считается за одно решение. При таком соглашении сравнение (1) будет иметь столько решений, сколько вычетов полной системы ему удовлетворяет.
Пример. Сравнению
x5 + x + 1 º 0 (mod 7)
среди чисел 0, 1, 2, 3, 4, 5, 6 полной системы вычетов по модулю 7 удовлетворяют два числа x = 2 и x = 4. Поэтому указанное сравнение имеет два решения:
x º 2 (mod 7), x º 4 (mod 7).
Из сравнений с одним неизвестным в дальнейшем будем рассматривать лишь простейшие, а именно сравнения первой степени, которые перенесением свободного члена (с обратным знаком) в правую часть можно привести к виду
ax º b (mod m). (2)
Рассмотрим вопрос о числе решений сравнения (2). Ответ на этот вопрос дают три нижеследующие теоремы.
Теорема. Если D(a, m) = 1, то сравнение (2) имеет единственное решение.
Доказательство. Наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю m, то ax пробегает полную систему вычетов (теорема 2). Следовательно, при одном и только одном значении x, взятом из полной системы ax будет сравнимо с b.
Теорема. Если D(a, m) = d и d не делит числа b, то сравнение (2) не имеет решений.
Доказательство. Это непосредственно следует из свойства 9 сравнений, хотя можно доказать следующим образом. Допустим, чтосуществует x0, удовлетворяющее этому сравнению:
ax0 º b (mod m).
Это можно записать в виде уравнения
ax0 – b = mt Þ ax0 – mt = b, где t – целое.
Здесь левая часть делится на d, а правая не делится, что невозможно.
Теорема. Если D(a, m) = d и b кратно d, то сравнение (2) имеет d решений. Все эти решения образуют один класс по модулю 
.
Доказательство. Пусть a = a1d, b = b1d, m = m1d. Тогда сравнение (2) будет равносильно такому (по сокращении на d) a1x º b1 (mod m1), в котором уже D(a1, m1) = 1, и потому оно будет иметь одно решение по модулю m1. Пусть x1 – наименьший неотрицательный вычет этого решения по модулю m1, тогда все числа x, образующие это решение, найдутся в виде
x º x1 (mod m1). (3)
По модулю же m числа (3) образуют не одно решение, а больше, именно столько решений, сколько чисел (3) найдется в ряде 0, 1, 2, ..., m – 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (3):
x1, x1 + m1, x1 + 2m1, ..., x1 + (d–1)m1,
т. е. всего d чисел (3); следовательно, сравнение (2) имеет d решений.
Рассмотрим один частный вид сравнения первой степени:
ax º 1 (mod m),
где D(a, m) = 1. Оно равносильно уравнению ax = 1 + mt Þ ax – mt = 1 Þ ax + mp = 1. Теперь нам необходимо подобрать числа x, p так, чтобы выполнялось это уравнение. А это позволяет сделать, рассматриваемый в следующем параграфе, обобщенный алгоритм Евклида.