Решение сравнений первой степени

 

Определение 10.1. Сравнением первой степени относительно неизвестного целого числа x называется сравнение вида

                                          ,                  (10.1)

где a, b  и m – целые числа. Если сравнение  верно, то число называется частным решением сравнения.

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

Рассмотрим сначала частный случай сравнений первой степени, а именно случай, когда правая часть сравнения равна 1.

Определение 10.2. Рассмотрим сравнение . Любое частное решение этого сравнения называется числом, обратным к числу a по модулю m.

Пример. Число 3 обратно к числу 2 по модулю 5, так как . Число  также является обратным к числу 2 по модулю 5 при любом целом t.

Теорема 10.1. Для того, чтобы существовало число x, обратное к числу a по модулю m, необходимо и достаточно, чтобы .

Доказательство. По теореме 5.1 (признаку взаимной простоты чисел) , для которых выполняется . Это равенство можно записать в виде: . Это и означает, что число u обратно к a по модулю m.

Как было установлено ранее, числа u и v можно находить при помощи алгоритма Евклида. Значит, алгоритм Евклида можно использовать для нахождения числа, обратного к данному.

Пример. Найти число, обратное к 26 по модулю 49.

Решим сравнение .

Поскольку , искомое число существует. Найдем НОД чисел 26 и 49, (который, как мы знаем, равен 1), по алгоритму Евклида.

Последний, отличный от 0, остаток и равен 1. Найдем его линейное представление:

Итак, получили, что .

Тогда – частное решение сравнения . Общим решением этого сравнения будут числа вида . Все числа такого вида и будут числами, обратными к 26 по модулю 49.

Вернемся теперь к общему случаю сравнения:

                                                            (10.1)

Теорема 10.2. Пусть . Для того, чтобы сравнение (10.1) имело решение, необходимо и достаточно, чтобы .

Доказательство. 1) Необходимость. Пусть сравнение  имеет решение . Тогда  – верно. Это означает, , где k  – целое число. Поскольку  по свойству НОД (теорема 3.3) ,

где . Тогда . Поскольку  – целое число, .

2) Достаточность. Пусть , тогда найдется такое целое число k, что . Поскольку  по свойству НОД (теорема 3.3) , где . Рассмотрим линейное представление числа 1 как НОД чисел  и  : . Умножим обе части равенства на d, получим , затем умножим обе части полученного равенства на k, получим . Отсюда следует, что . Значит, сравнение  имеет решение. Таким решением является, например, число .

Теорема 10.2 указывает путь к решению сравнений первой степени. Действительно, решение сравнения первой степени можно свести к решению неопределенного уравнения.

Пример. Решить сравнение . Решение этого сравнения существует, поскольку  и . Запишем сравнение в виде , где . Решим полученное неопределенное уравнение при помощи алгоритма Евклида, получим частное решение , где . Тогда решением исходного сравнения является множество чисел вида , где .

        Другой способ решения сравнений первой степени состоит в применении теоремы Эйлера. Рассмотрим сравнение . Не умаляя общности, можно считать, что . Действительно, если и , то по теореме 10.2 для существования решения сравнения необходимо и достаточно, чтобы . По свойству сравнений (следствие 1 к свойству 8) можно разделить обе части сравнения и модуль на их общий делитель . При этом частные от делений чисел a и m будут взаимно просты. Поэтому можно изначально предполагать, что .

    Тогда по теореме Эйлера . Умножим обе части сравнения на число b, получим . Запишем последнее сравнение в виде . Число , очевидно, является частным решением сравнения. Общее решение сравнения имеет вид: .

Пример. Решить сравнение . Поскольку , по теореме Эйлера . Положим . Найденное значение  является частным решением сравнения. Тогда общее решение сравнения имеет вид: . Заменим  на число, сравнимое с ним по модулю 3 и запишем ответ в упрощенном виде: .

    Итак, мы рассмотрели два способа решения сравнений. Первый способ сводит решение сравнения к решению неопределенного уравнения. Используя второй способ, мы можем наоборот свести решение неопределенного уравнения к решению сравнения. Рассмотрим неопределенное уравнение . Предположим, что  и . Тогда, как было установлено в § 6, данное уравнение имеет решение. Запишем уравнение в виде . Решив сравнение при помощи функции Эйлера, найдем частное решение . Подставив его в уравнение, найдем частное решение , а затем выпишем общее решение уравнения.

Пример. Решить уравнение . Из уравнения получим сравнение . Поскольку , сравнение имеет решение. Тогда  – частное решение сравнения. Упростим его, получим . Общее решение сравнения , . Подставим полученное частное решение  в уравнение: . Тогда частное решение , а общее решение , . Таким образом, мы получили общее решение уравнения: , .