Определение Множество натуральных чисел

2.2. Решение сравнений

Сравнение с одним неизвестным x имеет вид

Где . Если a_n не делится на m, то и называется степенью сравнения.
Решением сравнения называется всякое целое число x₀, для которого

Если х₀ удовлетворяет сравнению, то, согласно свойству 9 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с x₀ по модулю m. Поэтому все решения сравнения, принадлежащие одному классу вычетов по модулю т, будем рассматривать как одно решение. Таким образом, сравнение имеет столько решений, сколько элементов полной системы вычетов ему удовлетворяет.
Сравнения, множества решений которых совпадают, называются равносильными.


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

Сравнение первой степени с одним неизвестным х имеет вид

(2.2)
Теорема2.4. Для того чтобы сравнение имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на НОД(a, m).
Доказательство. Сначала докажем необходимость. Пусть d = НОД(a, m) и х₀— решение сравнения. Тогда , то есть разность ах₀−b делится на т. Значит, существует такое целое число q, что ах₀−b = qm. Отсюда b = ах₀−qm. А поскольку d, как общий делитель, делит числа а и т, то уменьшаемое и вычитаемое делятся на d, а значит и b делится на d.
Теперь докажем достаточность. Пусть d— наибольший общий делитель чисел а и т, и b делится на d. Тогда по определению делимости существуют такие целые числа a₁,b₁ ,т₁, что .
Расширенным алгоритмом Евклида найдем линейное представление числа 1 = НОД(a₁, m₁):

для некоторых x₀, y₀ . Домножим обе части последнего равенства на b₁d:

или, что то же самое,
,
то есть , и — решение сравнения. □
Пример2.10. Сравнение 9х = 6 (mod 12) имеет решение, так как НОД(9, 12) = 3 и 6 делится на 3. □
Пример2.11. Сравнение 6х = 9 (mod 12) не имеет решений, так как НОД(6, 12) = 6, а 9 не делится на 6. □
Теорема 2.5. Пусть сравнение (2.2) разрешимо и d = НОД(a, m). Тогда множество решений сравнения (2.2) состоит из d классов вычетов по модулю т, а именно, если х₀ — одно из решений, то все другие решения — это
Доказательство. Пусть х₀— решение сравнения (2.2), то есть и , . Значит, существует такое q , что ах₀−b = qm. Подставляя теперь в последнее равенство вместо х₀ произвольное решение вида , где , получаем выражение
, делящееся на m. □
Пример 2.12. Сравнение 9х=6 (mod 12) имеет ровно три решения, так как НОД(9, 12)=3. Эти решения: х₀ = 2, х₀ + 4 = 6, х₀ + 2∙4=10.□
Пример2.13. Сравнение 11х=2 (mod 15) имеет единственное решение х₀ = 7,таккакНОД(11,15)=1.□
Покажем, как решать сравнение первой степени. Не умаляя общности, будем считать, что НОД(a, т) = 1. Тогда решение сравнения (2.2) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел a и т:
.
Умножим обе части этого равенства на b, получим: b = abq + mrb, откуда abq - b = -mrb, то есть a ∙ (bq) = b(mod m) и bq— решение срав­нения (2.2).
Еще один путь решения — использовать теорему Эйлера. Опять считаем, что НОД(а, т)= 1. Применяем теорему Эйлера: . Умножим обе части сравнения на b: . Переписывая последнее выражение в виде , получаем, что — решение сравнения (2.2).
Пусть теперь НОД(a, m) =d>1.Тогда a = a_td, m = m_td, где НОД(а₁, m₁) = 1. Кроме того, необходимо b = b₁d, для того чтобы сравнение было разрешимо. Если х₀— решение сравнения а₁x = b₁(mod m₁), причем единственное, поскольку НОД(а₁, m₁) = 1, то х₀ будет решением и сравнения а₁xd = db₁(mod m₁), то есть исходного сравнения (2.2). Остальные d- 1 решений находим по теореме 2.5.